Min Cost Climbing Stairs

How it works

At each step, you only need the minimum cost of the next one or two steps. So instead of using a full DP array, we can reuse the input array and update it in place.

Each cost[i] is updated to represent:

the minimum cost to reach the top starting from step i.

By the end, the answer is simply the minimum cost starting from step 0 or 1.

Steps

1. Start from the third-last step and move backwards.
2. For each step i:
   • Update cost[i] = cost[i] + min(cost[i+1], cost[i+2])
3. After processing all steps:
   • Return min(cost[0], cost[1]) since you can start from either.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Misunderstanding the Goal Position

The top of the staircase is at index n (one step past the last stair), not at index n-1. You need to reach beyond the last step, so your DP array or recursion must account for landing on position n, not just visiting the last cost element.

Forgetting You Can Start from Step 0 or Step 1

The problem allows starting from either step 0 or step 1 without paying any cost initially. A common mistake is assuming you must start from step 0 only, which can lead to suboptimal solutions when starting from step 1 would be cheaper.

Incorrect Base Cases in DP

When using bottom-up DP, the base cases should be dp[0] = 0 and dp[1] = 0 because you can stand on step 0 or step 1 for free before paying to move forward. Setting these incorrectly, such as dp[0] = cost[0], misinterprets when you pay the cost.

from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])

        return min(cost[0], cost[1])

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        for (int i = cost.size() - 3; i >= 0; i--) {
            cost[i] += min(cost[i + 1], cost[i + 2]);
        }
        return min(cost[0], cost[1]);
    }
};