#746
Min Cost Climbing Stairs
Easy 1D DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
cost[i] is paid when you step on stair i, and you can then climb 1 or 2 stairs. You may start on stair 0 or 1. Return the minimum cost to get past the last stair.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: cheapest way to get past the top when each step has a cost.
Why this works: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
Example: cost [10, 15, 20]
dp[2] = min(0+15, 0+10) = 10dp[3] = min(10+20, 0+15) = 15
✦Hints open one at a time
Let dp[i] = minimum cost to stand on stair i (before paying it).
dp[i] = min(dp[i − 1] + cost[i − 1], dp[i − 2] + cost[i − 2]).
↗Approach
dp[0] = dp[1] = 0. Fill up to dp[n], the top (one past the last stair). Two variables are enough.
</>Solution (Java)
class Solution {
public int minCostClimbingStairs(int[] cost) {
int a = 0, b = 0; // dp[i-2], dp[i-1]
for (int i = 2; i <= cost.length; i++) {
int c = Math.min(b + cost[i - 1], a + cost[i - 2]);
a = b;
b = c;
}
return b;
}
}!Common mistake
Returning dp[n − 1] — the top is past the last stair, index n.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon