Min Cost Climbing Stairs

1. Define the problem

You are given an array cost where cost_i is the cost of stepping on stair i. Once you pay the cost, you can climb 1 or 2 steps. You can start from step 0 or step 1, and the top is one step past the last index. Return the minimum cost to reach the top. The cheapest way to reach step i is cost_i plus the cheaper of the two smaller subproblems already solved for step i-1 and step i-2 — the same overlapping subproblems pattern as counting ways, but tracking a running minimum instead of a running sum.

Constraints

2 ≤ cost.length ≤ 1000
0 ≤ cost_i ≤ 999

Example

Inputcost = [10, 15, 20]

Output15

Explanation Start on step 1 (cost 15) and jump straight to the top, which is cheaper than any path through step 0.

2. Visualize the solution

Track the cheaper of the two previous steps

step 010

step 115

step 2—

Statusbase

The whole table for cost = [10, 15, 20] is laid out. dp[0] = 10 and dp[1] = 15 are the base cases; dp[2] is still blank.

What happens in this step

cost = [10, 15, 20]
dp[0] = cost[0] = 10
dp[1] = cost[1] = 15

You can start at either step 0 or step 1, so both are seeded directly from their own cost. dp[2] has not been worked out yet.

Step 1 of 3

Steps to visualize

Set the base cases: dp₀ = cost₀ and dp₁ = cost₁.
For every step i from 2 onward, dp_i = cost_i + min(dp[i-1], dp[i-2]).
The answer is the cheaper of the final two steps, since the top can be reached from either.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track the cheaper of the two previous steps

step 010

step 115

step 2—

Statusbase

The whole table for cost = [10, 15, 20] is laid out. dp[0] = 10 and dp[1] = 15 are the base cases; dp[2] is still blank.

What happens in this step

cost = [10, 15, 20]
dp[0] = cost[0] = 10
dp[1] = cost[1] = 15

You can start at either step 0 or step 1, so both are seeded directly from their own cost. dp[2] has not been worked out yet.

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

function minCostClimbingStairs(cost) {
  const n = cost.length;
  let prev2 = cost[0];
  let prev1 = cost[1];

  for (let i = 2; i < n; i++) {
    const curr = cost[i] + Math.min(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
  }

  return Math.min(prev1, prev2);
}

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

5. Test cases

Test cases

Input	Expected	Covers
`cost = [10, 15, 20]`	`15`	example from the docstring
`cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]`	`6`	longer array where skipping expensive steps pays off
`cost = [1, 2]`	`1`	smallest valid array, just two steps
`cost = [5, 5, 5, 5]`	`10`	every step costs the same
`cost = [1, 2, 3, 4]`	`4`	strictly increasing costs
`cost = [0, 0, 0, 0, 0]`	`0`	every step is free
`cost = [3, 1, 2, 4, 1]`	`4`	mixed costs with no obvious pattern

Min Cost Climbing Stairs