---
Difficulty: Medium
Source: 160 Days of Problem Solving
Tags:
- Dynamic Programming
---
# π _Day 9. Min Cost Climbing Stairs_ π§
The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/dynamic-programming-gfg-160/problem/min-cost-climbing-stairs)
## π‘ **Problem Description:**
Given an array of integers `cost[]`, where `cost[i]` represents the cost of the `i-th` step on a staircase, you can either:
- Pay the cost at `i-th` step and move **one step** forward.
- Pay the cost at `i-th` step and move **two steps** forward.
Return the **minimum cost** required to reach the top of the floor.
π **Assumptions:**
- **0-based indexing**
- You can start either from **step 0** or **step 1**
## π **Example Walkthrough:**
### **Example 1:**
#### **Input:**
```cpp
cost[] = [10, 15, 20]
```
#### **Output:**
```cpp
15
```
#### **Explanation:**
The cheapest way is:
- Start at `cost[1] = 15`
- Jump **2 steps** to the top (no cost at the top)
### **Example 2:**
#### **Input:**
```cpp
cost[] = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
```
#### **Output:**
```cpp
6
```
#### **Explanation:**
The cheapest way is:
1 β 3 β 4 β 6 β 7 β 9 (Total cost = `1 + 1 + 1 + 1 + 1 + 1 = 6`)
## **Constraints:**
- $\(2 \leq \text{cost.length} \leq 1000\)$
- $2 β€ cost.size() β€ 10^5$
- $\(0 \leq \text{cost[i]} \leq 999\)$
## π― **My Approach:**
### **Algorithm Steps:**
1. **Use two variables** `a` and `b` to keep track of the **minimum cost** of the last two steps.
2. **Iterate through the cost array**, updating `b` using the recurrence relation:
- `b = cost[i] + min(a, b)`
- `a = previous b` (before update)
3. **Return** `min(a, b)`, representing the minimum cost to reach the top.
## π **Time and Auxiliary Space Complexity**
- **Expected Time Complexity:** `O(N)`, as we iterate through the `cost` array once.
- **Expected Auxiliary Space Complexity:** `O(1)`, as we use only a constant amount of extra space (`a` and `b`).
## π **Solution Code**
## **Code (C++)**
```cpp
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int a = cost[0], b = cost[1];
for (int i = 2; i < cost.size(); i++)
tie(a, b) = make_tuple(b, cost[i] + min(a, b));
return min(a, b);
}
};
```
β‘ Alternative Approaches
## **1οΈβ£ Dynamic Programming (O(N) Time, O(N) Space) β Tabulation**
### **Algorithm Steps:**
1. **Use an array `dp[]`** to store the minimum cost at each step.
2. **Base cases:**
- `dp[0] = cost[0]`
- `dp[1] = cost[1]`
3. **Recurrence relation:**
$\[
\text{dp[i]} = \text{cost[i]} + \min(\text{dp[i-1]}, \text{dp[i-2]})
$\]
```cpp
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int n = cost.size();
vector dp(n);
dp[0] = cost[0], dp[1] = cost[1];
for (int i = 2; i < n; i++)
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
return min(dp[n - 1], dp[n - 2]);
}
};
```
β
**Time Complexity:** `O(N)`
β
**Space Complexity:** `O(N)`
## **2οΈβ£ Recursive + Memoization (O(N) Time, O(N) Space)**
### **Algorithm Steps:**
1. **Use recursion with memoization** to avoid repeated calculations.
2. **Base cases:**
- If `i < 0`, return `0`
- If `i == 0 || i == 1`, return `cost[i]`
3. **Store computed results** in a `dp[]` array to prevent redundant calls.
```cpp
class Solution {
public:
vector dp;
int solve(vector& cost, int i) {
if (i < 0) return 0;
if (i == 0 || i == 1) return cost[i];
if (dp[i] != -1) return dp[i];
return dp[i] = cost[i] + min(solve(cost, i - 1), solve(cost, i - 2));
}
int minCostClimbingStairs(vector& cost) {
dp.assign(cost.size(), -1);
int n = cost.size();
return min(solve(cost, n - 1), solve(cost, n - 2));
}
};
```
β
**Time Complexity:** `O(N)`
β
**Space Complexity:** `O(N)`
## **3οΈβ£ Iterative Approach Without Extra Variables (O(N) Time, O(1) Space)**
### **Algorithm Steps:**
1. **Modify the input array `cost[]`** in-place to store the **cumulative minimum cost**.
```cpp
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
for (int i = 2; i < cost.size(); i++)
cost[i] += min(cost[i - 1], cost[i - 2]);
return min(cost[cost.size() - 1], cost[cost.size() - 2]);
}
};
```
β
**Time Complexity:** `O(N)`
β
**Space Complexity:** `O(1)`
## **Comparison of Approaches**
| **Approach** | β±οΈ **Time Complexity** | ποΈ **Space Complexity** | β
**Pros** | β οΈ **Cons** |
| ------------------------------------ | ---------------------- | ----------------------- | ----------------------------------- | ------------------------------- |
| **Iterative DP (Space Optimized)** | π‘ `O(N)` | π’ `O(1)` | Simple and fastest iterative method | Limited to Fibonacci-like logic |
| **Dynamic Programming (Tabulation)** | π‘ `O(N)` | π΄ `O(N)` | Easy to understand and implement | Consumes extra space |
| **Recursive + Memoization** | π‘ `O(N)` | π΄ `O(N)` | Natural recursive logic | Higher recursion overhead |
| **Iterative In-Place Update** | π‘ `O(N)` | π’ `O(1)` | No extra variables used | Modifies input array |
## π‘ **Best Choice?**
β
**For simplicity and efficiency:** Use **Iterative DP (Space Optimized)**.
β
**For an alternative approach without extra space:** Use **In-Place Iterative DP**.
β
**For understanding step-by-step execution:** Use **Tabulation DP**.
## **Code (Java)**
```java
class Solution {
public int minCostClimbingStairs(int[] cost) {
int a = cost[0], b = cost[1];
for (int i = 2; i < cost.length; i++) {
int temp = b;
b = cost[i] + Math.min(a, b);
a = temp;
}
return Math.min(a, b);
}
}
```
## **Code (Python)**
```python
class Solution:
def minCostClimbingStairs(self, cost):
for i in range(2, len(cost)):
cost[i] += min(cost[i - 1], cost[i - 2])
return min(cost[-1], cost[-2])
```
## π― **Contribution and Support:**
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
---
πVisitor Count
