Min Cost Climbing Stairs (2 jumps)

Easy Dynamic Programming 1D DP Original on LeetCode

Reported atAmerican Express

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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]).
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]).
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.
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.