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

Topic	Description
Dynamic Programming	Break a problem into overlapping subproblems and reuse their answers to avoid recomputing the same work.
Climbing Stairs	Count how many distinct ways you can climb a staircase taking one or two steps at a time.
Fibonacci Number	Compute the nth number in the Fibonacci sequence.
House Robber	Find the most money you can rob from a row of houses without robbing two next to each other.
Coin Change	Find the fewest coins needed to make up a given amount from a set of coin values.
Longest Increasing Subsequence	Find the length of the longest subsequence of an array that is strictly increasing.