Min Cost Climbing Stairs

Easy Problem 116 of 151 Java and Python

Problem

You are given an array cost where cost[i] is the cost of the i-th step. Once you pay a step's cost you may climb one or two steps. You can start on step 0 or step 1.

Return the minimum cost to reach the top, which is one past the last step.

Example 1

Input: cost = [10, 15, 20]
Output: 15
Why: Start at step 1, pay 15, jump two steps to the top.

Example 2

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

Constraints

2 ≤ cost.length ≤ 1000
0 ≤ cost[i] ≤ 999

Explanation

Let best(i) be the cheapest way to stand on step i (before paying it). You arrive from i - 1 (paying cost[i - 1]) or from i - 2 (paying cost[i - 2]). Steps 0 and 1 are free to start on.

The answer is best(n), the top. Only the last two values are needed at any time.

Approach 1 · Naive

Plain recursion

Time O(2ⁿ)
Space O(n) recursion

Compute best(i) = min(best(i - 1) + cost[i - 1], best(i - 2) + cost[i - 2]) recursively.

best(0) = best(1) = 0.
Return best(n).

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return best(cost, cost.length);
    }

    private int best(int[] cost, int i) {
        if (i <= 1) {
            return 0;
        }
        return Math.min(best(cost, i - 1) + cost[i - 1], best(cost, i - 2) + cost[i - 2]);
    }
}

Python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        def best(i):
            if i <= 1:
                return 0
            return min(best(i - 1) + cost[i - 1], best(i - 2) + cost[i - 2])

        return best(len(cost))

Approach 2 · Optimal

Bottom-up with two variables

Time O(n)
Space O(1)

Compute best(i) from 2 up to n, remembering only the previous two.

twoBack = oneBack = 0 (steps 0 and 1).
For i from 2 to n: current = min(oneBack + cost[i - 1], twoBack + cost[i - 2]); shift the variables.
Return oneBack.

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int twoBack = 0;
        int oneBack = 0;
        for (int i = 2; i <= cost.length; i++) {
            int current = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(2ⁿ)	O(n) recursion
Optimal Bottom-up with two variables	O(n)	O(1)

Key takeaways

Be precise about what the state means ("cost to stand on step i, not yet paid"); off-by-one errors come from a vague state.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem