Min Cost Climbing Stairs

Concept

LeetCode #746.
Problem: You are given an integer array cost where cost[i] is the cost of i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

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

• Start at index 1 (pay 15).
• Jump 2 steps to reach the absolute top.
• Total cost: 15.

This is the exact same problem as Climbing Stairs, but instead of tracking the “Number of Ways”, we are tracking the “Minimum Cost” path.

The DP Strategy

We create a dp Array.
dp[i] will represent the absolute minimum total cost required to physically land on step i.

Let’s look at a step i. How did we get there?
We either jumped from i - 1 or i - 2.
If we came from i - 1, the total cost would be the cost to reach i - 1 PLUS the toll we pay to stand on i - 1 before jumping.
path1 = dp[i - 1] + cost[i - 1]

If we came from i - 2, the total cost would be:
path2 = dp[i - 2] + cost[i - 2]

Because we want the absolute minimum cost, we use Math.min():
Recurrence Relation: dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

Implementation (Tabulation)

Notice that the “Top of the floor” is mathematically one index past the end of the cost array! If cost.length is 3, the top is index 3.

// Time Complexity: O(N)
// Space Complexity: O(N)

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const dp = new Array(n + 1); // +1 because we need to land strictly PAST the final step!

    // Base Cases: 
    // The problem states we can start at index 0 or index 1 for free!
    // We don't pay the toll until we JUMP from them.
    dp[0] = 0;
    dp[1] = 0;

    for (let i = 2; i <= n; i++) {
        // The absolute cheapest way to land on step i
        dp[i] = Math.min(
            dp[i - 1] + cost[i - 1], // The cost to land on i-1, PLUS the toll of i-1
            dp[i - 2] + cost[i - 2]  // The cost to land on i-2, PLUS the toll of i-2
        );
    }

    // Return the minimum cost to reach the very top
    return dp[n];
}

State Reduction ($O(1)$ Space)

Just like normal Climbing Stairs, dp[i] only relies on dp[i-1] and dp[i-2]. We can perfectly optimize this to $O(1)$ space by using two sliding pointers.

function minCostOptimized(cost: number[]): number {
    let twoBack = 0; // Cost to land on index 0
    let oneBack = 0; // Cost to land on index 1

    for (let i = 2; i <= cost.length; i++) {
        const currentCost = Math.min(
            oneBack + cost[i - 1],
            twoBack + cost[i - 2]
        );
        
        // Slide the pointers forward
        twoBack = oneBack;
        oneBack = currentCost;
    }

    return oneBack;
}

Interview Questions

Q: A developer tries to solve this using a Greedy approach: “Always jump to the step with the cheaper toll.” Does this work?
A: No, a Greedy algorithm completely fails this problem.
Imagine cost = [0, 100, 1, 1].
If you start at 0, Greedy sees 100 and 1. It jumps to 1 (index 2). Cost so far: 0 + toll(0) = 0.
Next step, it pays the toll at index 2 (1) to jump to the end. Total Cost: 1.
Wait! What if we just jumped 0 -> 100 -> End? That costs 100. Okay, Greedy won here.
But what if cost = [10, 15, 20]? Greedy starts at 10, jumps to 15, jumps to end. Cost: 10 + 15 = 25. The optimal DP path is 15 -> End (Cost: 15). Greedy fails because a cheap local step might force you onto a path with a massive future penalty. DP evaluates the entire path cost perfectly.