Min Cost Climbing Stairs (LeetCode 746)

The problem

You get an array cost, where cost[i] is the price of stepping off step i. You may start on step 0 or step 1 for free. From any step you climb 1 or 2 steps, paying that step’s cost. The “top” is just past the last step (index len(cost)). Return the minimum total cost to reach the top.

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

Start on step 1, pay 15, and jump two steps straight to the top. Paying 10 and 20 would cost 30.

How to think about it

Start with brute force. From each step, try both moves and recurse, returning the cheaper total. Like Climbing Stairs, the call tree branches twice per level, so it is O(2ⁿ) and recomputes the same steps many times.

The key insight: think about how you arrive. To stand on position i you came from i-1 (paying cost[i-1]) or from i-2 (paying cost[i-2]). So dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), where dp[i] is the cheapest way to stand on position i. The base cases are dp[0] = dp[1] = 0 because you may start on either for free.

Roll two variables. Each dp[i] uses only the previous two entries, so keep a = dp[i-2] and b = dp[i-1] and slide them forward. The answer is dp[len(cost)], the position just past the last step.

Which pattern is this? 1-D DP with a min instead of a sum. The tell is “minimum cost” with moves of 1 or 2, so each answer depends on a fixed number of earlier answers.

Approach

1. Set a = dp[0] = 0 and b = dp[1] = 0.
2. For i from 2 to len(cost): compute the new value min(b + cost[i-1], a + cost[i-2]), then shift so a becomes the old b and b becomes the new value.
3. Return b, which is dp[len(cost)].

Solution

def min_cost_climbing(cost):
    a, b = 0, 0                                   # dp[i-2], dp[i-1]: starting is free
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i-1], a + cost[i-2])   # arrive from one or two steps below
    return b
# min_cost_climbing([10,15,20]) -> 15

Dry run

On cost = [10, 15, 20]:

dp[3] = 15, so the answer is 15.

Complexity

• Time: O(n). One pass over the positions, constant work each.
• Space: O(1). Two variables replace the full dp array.

Edge cases and pitfalls

• Two steps only ([5, 3]): the loop runs once and returns min(0 + 3, 0 + 5) = 3.
• The top is past the last step. Returning dp[len(cost) - 1] is a common off-by-one; you must step off the last stair too.
• Mixing up “cost to stand on” and “cost to leave”. Here dp[i] excludes cost[i], which is why the recurrence adds the predecessor’s cost. Be consistent.
• Greedy (always take the cheaper next step) fails. A cheap step now can force an expensive one later; DP compares both paths fully.

Related problems

• Climbing Stairs (LeetCode 70): the counting version of the same recurrence.
• House Robber (LeetCode 198): another two-variable DP where each choice looks one or two places back.
• Minimum Path Sum (LeetCode 64): the same min-cost idea extended to a 2-D grid.