Naive Pseudo-code

text
function minCost(i):
    if i >= length of cost:
        return 0
    
    cost_one_step = minCost(i + 1)
    cost_two_steps = minCost(i + 2)
    
    return cost[i] + min(cost_one_step, cost_two_steps)

return min(minCost(0), minCost(1))

Complexity Analysis

The time complexity of this approach is O(2^n). Each call branches into two new recursive calls, creating a binary tree of execution. The space complexity is O(n) due to the recursion stack depth.

Why it Fails

This approach fails due to overlapping subproblems. The algorithm repeatedly recalculates the minimum cost for the same steps. For example, to find the cost for step 0, it calculates step 2. To find the cost for step 1, it also calculates step 2. As n grows (up to 1000 in this problem), the number of redundant calculations explodes exponentially, leading to a Time Limit Exceeded (TLE) error.

Core Insight for Min Cost Climbing Stairs

The core insight that transitions us from the naive recursive approach to the optimal solution is the realization that we can reverse the direction of calculation. Instead of looking forward from the start, we can look backward from the destination (or build forward from the start iteratively).

To reach step i, there are exactly two possibilities:

1. We came from step i-1 and paid cost[i-1].
2. We came from step i-2 and paid cost[i-2].

Therefore, the minimum cost to reach step i is the minimum of these two scenarios. This establishes our recurrence relation (the "transition equation"):

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

Here, dp[i] represents the minimum accumulated cost to arrive at step i.

Visual Description: Imagine an array dp of size n + 1. We know the cost to arrive at index 0 is 0 and index 1 is 0 (since we can start at either for free). To fill index 2, we look at the values at indices 0 and 1, add their respective traversal costs, and pick the smaller sum. We repeat this process linearly. The dependency graph is a straight line where node i only requires data from i-1 and i-2, allowing us to discard older data and optimize space.

Execution Flow

Let's trace the algorithm with cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1].

1. Initialization:

   • prev2 (cost to reach index 0) = 0
   • prev1 (cost to reach index 1) = 0
   • cost array length n = 10.

2. Iteration (i = 2 to 10):

   • i = 2:
     • From index 0: prev2 (0) + cost[0] (1) = 1
     • From index 1: prev1 (0) + cost[1] (100) = 100
     • Current min: 1
     • Update: prev2 becomes 0, prev1 becomes 1.
   • i = 3:
     • From index 1: prev2 (0) + cost[1] (100) = 100
     • From index 2: prev1 (1) + cost[2] (1) = 2
     • Current min: 2
     • Update: prev2 becomes 1, prev1 becomes 2.
   • i = 4:
     • From index 2: prev2 (1) + cost[2] (1) = 2
     • From index 3: prev1 (2) + cost[3] (1) = 3
     • Current min: 2 (Wait, 1+1=2 vs 2+1=3. Min is 2).
     • Update: prev2 becomes 2, prev1 becomes 2.
   • ... (Loop continues) ...

3. Termination:

   • The loop finishes when i reaches n. The variable prev1 holds the minimum cost to reach the "top".

Proof of Correctness

The correctness is guaranteed by mathematical induction.

• Base Case: The costs to reach step 0 and step 1 are trivially correct (0).
• Inductive Step: Assume that for all steps k < i, our algorithm has correctly computed the minimum cost to reach step k. To reach step i, one must come from either i-1 or i-2. Since we compare the optimal cost of reaching i-1 (plus the cost to leave it) against the optimal cost of reaching i-2 (plus the cost to leave it), and we choose the minimum, the result for i must also be optimal.
• Since the base cases are optimal and the inductive step preserves optimality, the final result at step n is correct.

Reference Implementation

C++ Solution for LeetCode 746

cpp
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // Base cases: cost to reach index 0 is 0, index 1 is 0.
        int prev2 = 0; // Represents dp[i-2]
        int prev1 = 0; // Represents dp[i-1]
        
        for (int i = 2; i <= n; ++i) {
            // Cost to reach current step i
            // We pay cost[i-1] if coming from i-1
            // We pay cost[i-2] if coming from i-2
            int current = min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            
            // Shift pointers for next iteration
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};

Java Solution for LeetCode 746

java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // Base cases implicitly handled:
        // To reach index 0: 0 cost
        // To reach index 1: 0 cost
        int prev2 = 0; // dp[i-2]
        int prev1 = 0; // dp[i-1]
        
        for (int i = 2; i <= n; i++) {
            int current = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

Python Solution for LeetCode 746

python
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # prev2 represents minimum cost to reach i-2
        prev2 = 0
        # prev1 represents minimum cost to reach i-1
        prev1 = 0
        
        for i in range(2, n + 1):
            # Calculate cost to reach current step i
            current = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
            
            # Shift variables for the next iteration
            prev2 = prev1
            prev1 = current
            
        return prev1