491. Min Cost Climbing Stairs
You are given an array of integers cost, where cost[i] is the toll you pay for standing on step i of a staircase. After paying a step's toll you may climb one or two steps further.
You may begin on step 0 or step 1 for free — the toll is only charged when you launch off a step. The "top" is the landing past the last step (position cost.length), and it charges nothing. Return the smallest total toll that gets you to the top.
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Start on step 1, pay 15, and jump two steps — that lands past step 2, which is the top. Total: 15. Starting at step 0 costs at least 10 + 20 or 10 + 15.
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Start on step 0 and hop two at a time onto the cheap steps: pay at indices 0, 2, 4, 6, 7, 9 for 1 + 1 + 1 + 1 + 1 + 1 = 6, skipping every 100.
Constraints:
- 2 ≤ cost.length ≤ 1000
- 0 ≤ cost[i] ≤ 999
Hints:
Think backwards from a step: once you are standing on step i, you must pay cost[i], and then your remaining bill is the cheaper of the bills from step i+1 or step i+2.
Define dp[i] = cheapest total to reach the top starting from step i. Then dp[i] = cost[i] + min(dp[i+1], dp[i+2]), with dp equal to 0 past the end. The answer is min(dp[0], dp[1]) because you may start on either.
Fill dp from the back in one loop — and notice you only ever look two slots ahead, so two variables replace the whole array.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: cost = [10, 15, 20]
Expected output: 15