|
This post is completed by 4 users
|
Add to List |
549. 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. You 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(2n).
Output:
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)
Output:
costs : [10, 1, 1, 15, 2, 30, 3] Minimum cost to reach top: 7