This post is completed by 2 users

  • 0
Add to List

Dynamic Programming - Minimum Cost for Climbing Stairs

Given the staircase and cost for each stair. Once you pay the cost at a step you can climb one or two stairs. Yor are allowed to start from any of the first two stairs. Your task is to reach to the top of the staircase by paying the minimum cost.


costs = [10, 12, 14, 20, 7]
minimum cost = 31
10 -- 14 -- 7

costs = [10, 1, 1, 15, 2, 30, 3]
minimum cost = 7
1 -- 1-- 2 -- 3


If you look closely, for each stage you have two options,whether to take one stair or two stairs. So you will try out all the options at every stage and will pick the minimum out of it. The problem is time complexity will be very high - O(2n).

Recursive Code:


minimum cost: 7

Dynamic Programming: Bottom-up

Initialize dp[] as the same length as the cost array. dp[i] will represent the minimum cost required to reach the ith index and it will be calculated as dp[i] = cost[i] + min(dp[i-1], dp[i-2]) Base case would be dp[0] = cost[0] and dp[1] = cost[1].

Time Complexity: O(N)

See the code below for more understanding.

DP Code:


costs : [10, 1, 1, 15, 2, 30, 3]
Minimum cost to reach top: 7

Also Read: