This post is completed by 2 users

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.
Example:
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
Approach:
Recursion:
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(2^{n}).
Recursive Code:
Output:
minimum cost: 7
Dynamic Programming: Bottomup
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[i1], dp[i2]) 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:
Output:
costs : [10, 1, 1, 15, 2, 30, 3] Minimum cost to reach top: 7
Also Read: