Min Cost Climbing Stairs

The key idea

The cheapest way to reach a stair is the smaller of the two cheapest ways to reach the two stairs below it, plus that stair's own cost. Build this answer from the bottom up, and the top is one step beyond the last stair.

Problem

You are given an integer array cost where cost[i] is the cost of stepping on the i-th stair. Once you pay the cost, you can climb either one or two steps.

You can start from the stair at index 0, or the stair at index 1.

Return the minimum cost to reach the top of the floor, which is one step beyond the last stair.

Constraints

2 <= cost.length <= 1000
0 <= cost[i] <= 999

Examples

Input: cost = [10,15,20] Output: 15

Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →