Minimum Cost Climbing Stairs
Minimum Cost to Climb Stairs
You are given an array of integers, `cost`, where `cost[i]` represents the cost of stepping from the (i)th floor of a staircase. After paying the cost, you can move to either the (i+1)th floor or the (i+2)th floor.
You can start at either the 0th or the 1st floor.
Your task is to determine the minimum cost required to reach the top of the staircase, which is just beyond the last floor in the `cost` array.
Output: 2
Explanation: We can start at index = 1 and pay the cost of cost[1] = 2 and take two steps to reach the top. The total cost is 2.
Constraints:
- 2 <= cost.length <= 100
- 0 <= cost[i] <= 100
Minimum Cost Climbing Stairs Solution
There are mainly 4 approach to solve this problem:
- Recursion Method
- Dynamic Programming – Top Down
- Dynamic Programming – Bottom Up
- Dynamic Programming – Space Optimized
1. Recursion Method
Solve the problem by breaking it into smaller sub problems and calculating the cost recursively for each possible step. This approach is simple but can be slow due to repeated calculations.
- Time complexity: O(2^n)
- Space complexity: O(n)
Code
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
return min(dfs(cost, 0), dfs(cost, 1));
}
int dfs(vector& cost, int i) {
if (i >= cost.size()) {
return 0;
}
return cost[i] + min(dfs(cost, i + 1),
dfs(cost, i + 2));
}
};
public class Solution {
public int minCostClimbingStairs(int[] cost) {
return Math.min(dfs(cost, 0), dfs(cost, 1));
}
private int dfs(int[] cost, int i) {
if (i >= cost.length) {
return 0;
}
return cost[i] + Math.min(dfs(cost, i + 1),
dfs(cost, i + 2));
}
}
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
def dfs(i):
if i >= len(cost):
return 0
return cost[i] + min(dfs(i + 1), dfs(i + 2))
return min(dfs(0), dfs(1))
class Solution {
minCostClimbingStairs(cost) {
const dfs = (i) => {
if (i >= cost.length) {
return 0;
}
return cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
}
return Math.min(dfs(0), dfs(1));
}
}
2. Dynamic programming Top Down Method
Use recursion with memorization to store results of previously solved sub problems, avoiding redundant calculations and improving efficiency.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector memo;
int minCostClimbingStairs(vector& cost) {
memo.resize(cost.size(), -1);
return min(dfs(cost, 0), dfs(cost, 1));
}
int dfs(vector& cost, int i) {
if (i >= cost.size()) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
memo[i] = cost[i] + min(dfs(cost, i + 1),
dfs(cost, i + 2));
return memo[i];
}
};
public class Solution {
int[] memo;
public int minCostClimbingStairs(int[] cost) {
memo = new int[cost.length];
Arrays.fill(memo, -1);
return Math.min(dfs(cost, 0), dfs(cost, 1));
}
private int dfs(int[] cost, int i) {
if (i >= cost.length) {
return 0;
}
if (memo[i] != -1) {
return memo[i];
}
memo[i] = cost[i] + Math.min(dfs(cost, i + 1),
dfs(cost, i + 2));
return memo[i];
}
}
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
memo = [-1] * len(cost)
def dfs(i):
if i >= len(cost):
return 0
if memo[i] != -1:
return memo[i]
memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
return memo[i]
return min(dfs(0), dfs(1))
class Solution {
minCostClimbingStairs(cost) {
const memo = new Int32Array(cost.length).fill(-1);
const dfs = (i) => {
if (i >= cost.length) {
return 0;
}
if (memo[i] !== -1) {
return memo[i];
}
memo[i] = cost[i] + Math.min(dfs(i + 1),
dfs(i + 2));
return memo[i];
}
return Math.min(dfs(0), dfs(1));
}
}
3. Dynamic Programming Bottom Up Method
Build the solution iteratively from the smallest sub problem to the full problem, calculating costs step by step and storing them in an array.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int n = cost.size();
vector dp(n + 1);
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];
}
};
public 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 {
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];
}
}
4. Dynamic programming Space Optimized Method
Improve the Bottom-Up approach by using only two variables instead of an entire array, reducing space usage while still computing the minimum cost.
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
for (int i = cost.size() - 3; i >= 0; i--) {
cost[i] += min(cost[i + 1], cost[i + 2]);
}
return min(cost[0], cost[1]);
}
}; public class Solution {
public int minCostClimbingStairs(int[] cost) {
for (int i = cost.length - 3; i >= 0; i--) {
cost[i] += Math.min(cost[i + 1], cost[i + 2]);
}
return Math.min(cost[0], cost[1]);
}
}
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])class Solution {
/**
* @param {number[]} cost
* @return {number}
*/
minCostClimbingStairs(cost) {
for (let i = cost.length - 3; i >= 0; i--) {
cost[i] += Math.min(cost[i + 1], cost[i + 2]);
}
return Math.min(cost[0], cost[1]);
}
}
