Min Cost Climbing Stairs
EasyDynamic Programming
You are given an array cost, where cost[i] is the price you pay whenever you stand on step i of a staircase.
You may start on step 0 or step 1 (you pay for the step you start on). From any step you can climb 1 or 2 steps. The top is the position just past the last step (index cost.length) and costs nothing to reach.
Return the minimum total cost to reach the top.
Example 1
- Input:
- cost = [3, 8, 2, 7, 1]
- Output:
- 6
- Explanation
- Start on step 0 (pay 3), jump to step 2 (pay 2), jump to step 4 (pay 1), then climb one step to the top. The total is 3 + 2 + 1 = 6.
Example 2
- Input:
- cost = [5, 9]
- Output:
- 5
- Explanation
- Start on step 0 (pay 5) and climb two steps straight to the top, never paying the 9.
Example 3
- Input:
- cost = [1, 7, 1, 7, 1, 7]
- Output:
- 3
- Explanation
- Land only on the 1s at steps 0, 2 and 4, then jump two steps from step 4 to the top.
Constraints
- 2 ≤
cost.length≤ 1000 - 0 ≤
cost[i]≤ 999