Approach Summary
dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Result is min(dp[n-1], dp[n-2]).
How to Recognize This Pattern
- Pay cost to leave stair, can start at 0 or 1
- Classic 1D DP with two choices
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Dynamic Programming