296. Min Cost Climbing Stairs

The cheapest way to stand on step i is its own cost plus the cheaper of the two steps you could have jumped from (i-1 or i-2).

Definition

Let dp[i] = the minimum cost to stand on step i. To stand on step i you must have jumped from step i-1 or step i-2, then paid cost[i]:

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

The top is one step past the last index, reachable from either of the last two steps for free, so the answer is min(dp[n-1], dp[n-2]).

Base cases

dp[0] = cost[0], dp[1] = cost[1] — you may start on either without paying to arrive.

Worked example

cost = [10, 15, 20]:

• dp[0] = 10, dp[1] = 15.
• dp[2] = 20 + min(15, 10) = 30.
• Answer = min(dp[2], dp[1]) = min(30, 15) = 15 (start at index 1, jump two steps to the top).

Complexity

• Time: O(n) — one transition per step.
• Space: O(n) for the table, reducible to O(1) with two rolling variables.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = cost[0], prev1 = cost[1];
        for (int i = 2; i < n; i++) {
            int cur = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = cur;
        }
        return Math.min(prev1, prev2);
    }
}