LeetCode #746 Easy

Min Cost Climbing Stairs

Pay cost[i] to leave step i, moving one or two steps at a time; reach past the top for the least total cost.

dynamic-programmingarray

02

Intuition

💡

It is easy to misread where this starts and stops. You may begin standing on step 0 OR step 1 for free, and the goal is not the last step, it is the floor PAST the last step. If dp[i] is the cheapest cost to reach step i, the top is step n, reachable by paying cost[n-1] to leave step n-1 or cost[n-2] to leave step n-2. Grabbing dp[n-1] as the final answer looks tempting because it is the last real step, but that pays for a hop you may never have needed to take, and just as often undercounts by ignoring the final payment entirely. The fix is to size the dp array through index n and always read dp[n] at the end. The invariant: dp[i] is the minimum cost to arrive at step i, built from the cheaper of its two possible predecessors.

03

Approach

1

Base cases

dp[0] = 0 and dp[1] = 0, since you can start standing on either step 0 or step 1 without paying anything to get there.

2

Fill forward

For each step i from 2 to n, dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) -- you either climbed one step from i-1 (paying cost[i-1]) or hopped two from i-2 (paying cost[i-2]), and you take whichever total is cheaper.

3

Read the goal, not the last step

The staircase has n steps (indices 0..n-1), but the goal is the floor one step past index n-1, i.e. index n. dp[n] already accounts for paying to leave whichever of the last two steps was cheaper, so it is read directly as the answer.

04

Solution & live demo

python

▶1class Solution:
▶2    def minCostClimbingStairs(self, cost: list[int]) -> int:
▶3        n = len(cost)
▶4        dp = [0] * (n + 1)
▶5        for i in range(2, n + 1):
▶6            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
▶7        return dp[n]

05

Edge cases

Only two steps

dp[0] = dp[1] = 0, so dp[2] = min(cost[0], cost[1]) -- you pay for exactly one step no matter which you start on.

A very expensive step in the middle

The min() at each fill step naturally routes around it by hopping two steps instead of landing on it.

All costs equal

Every path costs the same per step taken; the DP still finds the path using the fewest steps, which ties out to the same total.

Reading dp[n-1] instead of dp[n]

Doing so stops one step short of the goal and silently pays for a move that was never required -- the goal is always dp[n].

06

Complexity

Time

O(n)

Space

O(n), or O(1) with two rolling variables

Single forward pass; each step reads only the previous two entries.