Min Cost Climbing Stairs (2 jumps)
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Recursion | O(2ⁿ) | O(n) |
| Tabulation | O(n) | O(n) |
| Optimal (two variables) | O(n) | O(1) |
1Recursion
O(2ⁿ)O(n)The cheapest way to reach step i comes from i - 1 or i - 2. Try both.
- reach(i) = 0 for i < 2 (free start).
- 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]);
}
}class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
return self.reach(cost, len(cost))
def reach(self, c: List[int], i: int) -> int:
if i < 2:
return 0
return min(self.reach(c, i - 1) + c[i - 1], self.reach(c, i - 2) + c[i - 2])class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
return reach(cost, cost.size());
}
private:
int reach(vector<int>& c, int i) {
if (i < 2) return 0;
return min(reach(c, i - 1) + c[i - 1], reach(c, i - 2) + c[i - 2]);
}
};function minCostClimbingStairs(cost) {
function reach(c, i) {
if (i < 2) return 0;
return Math.min(reach(c, i - 1) + c[i - 1], reach(c, i - 2) + c[i - 2]);
}
return reach(cost, cost.length);
}2Tabulation
O(n)O(n)dp[i] = minimum cost to arrive at position i (the top is position n).
- dp[0] = dp[1] = 0.
- 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];
}
}class Solution:
def minCostClimbingStairs(self, 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]class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1, 0);
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];
}
};function minCostClimbingStairs(cost) {
const n = cost.length;
const dp = new Array(n + 1).fill(0);
for (let 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)
O(n)O(1)Only dp[i - 1] and dp[i - 2] are needed.
- 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;
}
}class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
a, b = 0, 0
for i in range(2, len(cost) + 1):
c = min(b + cost[i - 1], a + cost[i - 2])
a = b
b = c
return bclass Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a = 0, b = 0;
for (int i = 2; i <= (int)cost.size(); i++) {
int c = min(b + cost[i - 1], a + cost[i - 2]);
a = b;
b = c;
}
return b;
}
};function minCostClimbingStairs(cost) {
let a = 0, b = 0;
for (let i = 2; i <= cost.length; i++) {
const 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.