Min Cost Climbing Stairs

Each step has a cost to step on; you can start at step 0 or 1 and climb 1 or 2 at a time. The cheapest way to reach step i is min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]). The top is one past the last step.

Traced input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] → 6. Original problem: neetcode.io/problems/min-cost-climbing-stairs

Complexity

Can be reduced to O(1) with two variables.

Key idea

• dp[i] = cheapest cost to stand on step i (before paying its own cost).
• dp[0] = dp[1] = 0: you can start on either for free.
• The answer is dp[n], the floor above the last step.

Common mistakes

• Returning dp[n−1] instead of dp[n].
• Charging the cost of the step you land on instead of the one you leave.

Solution

int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

def minCostClimbingStairs(cost: List[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    return dp[n]

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1);
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

Edge cases

Each one has its own trace in the interactive view.