Min Cost Climbing Stairs
You are given an array of non-negative integers representing the cost of climbing each step on a staircase. At each step, you can either climb 1 or 2 steps. In the beginning, you can either climb from the 0th step or the 1st step. Your goal is to find the minimum cost to reach the top of the staircase.
Constraints:
- 1 <= cost.length <= 1000
- 0 <= cost[i] <= 999
Examples:
Input: [10, 15, 20]
Output: 15
Explanation: You can climb from the 0th step to the 1st step with a cost of 10, then from the 1st step to the 2nd step with a cost of 5, for a total cost of 15.
Solutions
Dynamic Programming
We use dynamic programming to solve this problem. We create an array dp where dp[i] represents the minimum cost to reach the ith step. We initialize dp[0] and dp[1] with the cost of the 0th and 1st steps respectively. Then we iterate from the 2nd step to the nth step, and for each step, we calculate the minimum cost to reach that step by taking the minimum of the cost to reach the previous step and the step before that, and add the cost of the current step. Finally, we return the minimum cost to reach the last step or the second last step.
function minCostClimbingStairs(cost) {
let n = cost.length;
let dp = new Array(n).fill(0);
dp[0] = cost[0];
dp[1] = cost[1];
for (let i = 2; i < n; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
return Math.min(dp[n - 1], dp[n - 2]);
}
Follow-up:
What if we can climb 3 steps at a time?
