4.23.2 — Min Cost Climbing Stairs

LeetCode 746 · Easy

The problem

cost[i] is what you pay to step off stair i. From a stair you may move one or two stairs up. You may start at index 0 or index 1, and you must reach the top — one past the last stair. Return the minimum total cost.

cost = [10,15,20]           →  15    (start at 1, pay 15, jump 2 to the top)
cost = [1,100,1,1,1,100,1,1,100,1]   →  6

The pattern

Identical to 4.23.1 Climbing Stairs with one operator changed. Counting used +; optimising uses min.

Let dp[i] be the cheapest way to reach stair i. You arrive from i − 1 or from i − 2, and reaching either of those already cost something, plus the price of stepping off it:

dp[i] = \min\big(dp[i-1] + cost[i-1],\ \ dp[i-2] + cost[i-2]\big)

Read it in words: the cheapest way here is the cheaper of arriving from one below or two below, in each case paying that stair's exit price.

dp[0] = dp[1] = 0, because starting at either is free.

The answer is dp[n], not dp[n-1] — the top is one past the last stair. That off-by-one is the whole trap in this problem.

The definition that decides everything

There are two ways to define the state and they lead to different-looking code:

• dp[i] = cheapest cost to reach stair i (used here). You pay when you leave.
• dp[i] = cheapest cost to reach the top starting from stair i. Then dp[i] = cost[i] + min(dp[i+1], dp[i+2]), the loop runs backwards, and the answer is min(dp[0], dp[1]).

Both are correct. Pick one, say it out loud, and stay consistent. Mixing the two mid-solution is where the off-by-one errors come from, and it is far more common than getting the recurrence wrong.

The solution

Python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        prev, curr = 0, 0                    # dp[0], dp[1] — both free to start

        for i in range(2, len(cost) + 1):
            prev, curr = curr, min(curr + cost[i - 1], prev + cost[i - 2])

        return curr                          # dp[n], the top

TypeScript

function minCostClimbingStairs(cost: number[]): number {
  let prev = 0, curr = 0;

  for (let i = 2; i <= cost.length; i++) {
    [prev, curr] = [curr, Math.min(curr + cost[i - 1], prev + cost[i - 2])];
  }

  return curr;
}

The loop runs to len(cost) inclusive, because the top is index n and that is the value you want.

prev and curr hold dp[i-2] and dp[i-1] at the top of each iteration. Only two cells are ever read, so no array is needed — form 4 from 4.22.

The simultaneous assignment keeps prev available while curr is being recomputed.

If the two variables feel error-prone, write the array version first and collapse it afterwards:

dp = [0] * (len(cost) + 1)
for i in range(2, len(cost) + 1):
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[-1]

Identical, easier to check, O(n) space. In an interview, write this one and then offer the O(1) version.

Trace

cost = [10, 15, 20]

i	from i−1	from i−2	dp[i]
2	dp[1] + cost[1] = 0 + 15 = 15	dp[0] + cost[0] = 0 + 10 = 10	10
3	dp[2] + cost[2] = 10 + 20 = 30	dp[1] + cost[1] = 0 + 15 = 15	15

Answer 15, matching the expected output. Note that stair 2 is cheapest to reach at 10, but the best route to the top skips it entirely.

Complexity

O(n) time, O(1) space.

Where this goes next

• Climbing Stairs — the counting version. min becomes +. 4.23.1.
• House Robber — the same two-variable rolling shape, with the twist that choosing a value forbids the neighbouring one. 4.23.3.
• Minimum Path Sum, Triangle — the same idea in two dimensions.

The operator table is worth memorising, because it is the only thing that changes between a large family of problems:

the question asks	the operator
how many ways	+
cheapest / fewest	min
best / largest	max
is it possible	or

Same recurrence shape, four different questions.

What the interviewer will push on

"What does dp[i] mean?" Say it in words before writing anything. This is the question, and vague answers here produce the off-by-one.

"Why does the loop go to n and not n − 1?" The top is one past the last stair.

"Can you define the state the other way round?" Yes — cost from i to the top, running backwards. Both work.

"O(1) space?" Two variables.

"What if you could climb up to k stairs?" Minimise over the previous k cells. A monotonic deque keeps it O(n) instead of O(nk) — the structure from 4.6.6.

One thing to volunteer: state the state definition and the base cases before the recurrence. Most wrong DP answers have the right recurrence and the wrong base or boundary.

Next: 4.23.3 House Robber — the first problem where a choice now removes an option later, which is the tell that greedy will fail.