Start practising

Min Cost Climbing Stairs (2 jumps)

Easy Dynamic Programming 1D DP Original on LeetCode

Min Cost Climbing Stairs (2 jumps) is a easy dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (two variables), runs in O(n) time and O(1) space. Below are 3 approaches in Java, from recursion up.

Problem

Step i costs cost[i] to stand on. From a step you can climb 1 or 2 steps. You can start at step 0 or 1. Return the minimum cost to reach the top (just past the last step).

Examples

Example 1

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

Example 2

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

Constraints

  • 2 <= cost.length <= 1000
  • You may start at step 0 or step 1; the top is just past the last step.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
RecursionO(2ⁿ)O(n)
TabulationO(n)O(n)
Optimal (two variables)O(n)O(1)

1Recursion

TimeO(2ⁿ)
SpaceO(n)

The cheapest way to reach step i comes from i - 1 or i - 2. Try both.

  1. reach(i) = 0 for i < 2 (free start).
  2. reach(i) = min(reach(i - 1) + cost[i - 1], reach(i - 2) + cost[i - 2]).
Java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return reach(cost, cost.length);
    }

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

2Tabulation

TimeO(n)
SpaceO(n)

dp[i] = minimum cost to arrive at position i (the top is position n).

  1. dp[0] = dp[1] = 0.
  2. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]).
Java
class Solution {
    public 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];
    }
}

3Optimal (two variables)

TimeO(n)
SpaceO(1)

Only dp[i - 1] and dp[i - 2] are needed.

  1. a = b = 0; roll forward.
Java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;
        for (int i = 2; i <= cost.length; i++) {
            int c = Math.min(b + cost[i - 1], a + cost[i - 2]);
            a = b;
            b = c;
        }
        return b;
    }
}

Edge cases to test

  • Two steps only

Hints

Hint 1

dp[i] = cheapest cost to stand on step i = cost[i] + min(dp[i - 1], dp[i - 2]).

FAQ

What is the best time complexity for Min Cost Climbing Stairs (2 jumps)?

Optimal (two variables) runs in O(n) time and O(1) extra space.

Which pattern does Min Cost Climbing Stairs (2 jumps) use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Minimal Cost (k jumps).

Is there a brute force solution for Min Cost Climbing Stairs (2 jumps)?

Yes. Recursion takes O(2ⁿ) time and O(n) space. The cheapest way to reach step i comes from i - 1 or i - 2.

Which edge cases should I test for Min Cost Climbing Stairs (2 jumps)?

Two steps only.