Min Cost Climbing Stairs
You get a list cost where cost[i] is the price you pay to climb off step i. Once you pay it you may climb one step or two steps.
You may start on step 0 or on step 1. The top of the stairs is the position just beyond the last step. Return the smallest total price to reach the top.
Examples
Input cost = [10, 15, 20]
Output 15
Start on step 1, pay 15, jump two to the top.
Input cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output 6
Use the cheap steps 0, 2, 4, 6, 7 and 9.
Input cost = [0, 0]
Output 0
Constraints
- 2 <= cost.length <= 1,000
- 0 <= cost[i] <= 999
Stuck? Take one hint at a time
Common mistakes
- Returning best[last] alone, which forgets that you can reach the top from the second to last step.
- Starting the table with best[0] = 0, which ignores the price of the first step.
- Paying cost[i] on arrival instead of when you climb off, which changes how the first and last steps are counted.
- Treating the top as step n and also adding a cost for it, when it has no price.
Questions an interviewer may ask next
- Allow jumps of one, two or three steps. What changes in the recurrence?
- Print the steps you stand on, not just the cost. (Remember which earlier step each best came from.)
- You may start on any step. How does the answer change?
- Solve it top down with recursion and a cache, and compare the two styles.
cost
[10,15,20]
Expected output
15
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.