Min Cost Climbing Stairs

Problem in plain words

Each stair i has a price cost[i] that you pay when you step off it. From any stair you may climb one or two stairs. You can begin on stair 0 or stair 1 for free, and the goal is to get past the last stair (the 'top', at index n). Find the cheapest total.

For example, with cost = [5, 2, 6], start on stair 1, pay 2, and jump two stairs to the top. Total: 2.

Intuition

To stand on stair i, your last move came either from stair i - 1 (paying its cost) or from stair i - 2 (paying that cost). Whichever of those two options is cheaper is the best way to reach i. Because each value only needs the two before it, this is the same rolling-window structure as the bottom-up Fibonacci DP lesson.

Approach

1. State: reach[i] is the minimum money spent to stand on stair i (with i = n meaning the top).
2. Recurrence: reach[i] = min(reach[i - 1] + cost[i - 1], reach[i - 2] + cost[i - 2]).
3. Base cases: reach[0] = 0 and reach[1] = 0, because you may start on either for free.
4. Order: compute i = 2 to n, keeping only the last two values. The answer is reach[n].

Dry run

Input: cost = [3, 1, 4, 1, 5], so the top is index 5.

The best route starts on stair 1, pays 1 to reach stair 3, pays 1 again to jump to the top. Total 2.

Java solution

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int twoBack = 0, oneBack = 0;   // reach[i-2], reach[i-1]
        for (int i = 2; i <= cost.length; i++) {
            int current = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Python solution

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        two_back, one_back = 0, 0   # reach[i-2], reach[i-1]
        for i in range(2, len(cost) + 1):
            current = min(one_back + cost[i - 1], two_back + cost[i - 2])
            two_back, one_back = one_back, current
        return one_back

Complexity

Edge cases and common mistakes

• The top is not the last stair: the answer is for index n, one past the end. Returning reach[n - 1] misses the final jump.
• Two stairs only: with cost = [a, b] the loop runs once and returns min(a, b), which is right.
• Paying for the starting stair twice: in this formulation you pay a stair's cost when leaving it, never when arriving.
• Mixing formulations: another common version defines dp[i] = cost[i] + min(dp[i-1], dp[i-2]) and returns min(dp[n-1], dp[n-2]). Both are correct; just do not combine pieces of each.