# Min Cost Climbing Stairs
**Difficulty:** EASY
[External](https://leetcode.com/problems/min-cost-climbing-stairs)
Canonical: https://scaleengineer.com/dsa/problems/min-cost-climbing-stairs
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index `0`, or the step with index `1`.

Return _the minimum cost to reach the top of the floor_.

**Example 1:**

**Input:** cost = [10,15,20]
**Output:** 15
**Explanation:** You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

**Example 2:**

**Input:** cost = [1,100,1,1,1,100,1,1,100,1]
**Output:** 6
**Explanation:** You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

**Constraints:**

* `2 <= cost.length <= 1000`
* `0 <= cost[i] <= 999`

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's definition into a recursive function. We define a function that calculates the minimum cost from a given step `i` to the top. The cost from step `i` is its own cost plus the minimum of the costs from the two subsequent steps (`i+1` and `i+2`). The final answer is the minimum of starting at step 0 or step 1. This method is simple to understand but suffers from re-calculating the same subproblems multiple times, leading to exponential complexity.
**Time:** O(2^n) - For each step, we make two recursive calls. This creates a recursion tree of height `n`, with approximately `2^n` nodes, leading to an exponential number of function calls. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be up to `n` in the worst case.
**Pros:** Simple to conceptualize and implement.; Closely follows the mathematical recurrence relation of the problem.
**Cons:** Extremely inefficient due to exponential time complexity.; Leads to a 'Time Limit Exceeded' error on most platforms for even moderately sized inputs.
### Explanation
The brute-force recursive approach solves the problem by exploring all possible paths to the top. For each step, it makes two recursive calls, one for taking a single step and one for taking two steps. This creates a binary recursion tree.

For example, to find the cost from step `i`, we calculate `cost[i] + min(solve(i+1), solve(i+2))`. This process continues until we reach or pass the top of the staircase (index `n`), at which point the cost is zero. The main drawback is that the cost for a particular step, `solve(k)`, will be computed every time the path-finding process reaches step `k`, leading to a massive number of redundant calculations.

```java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        return Math.min(solve(cost, 0), solve(cost, 1));
    }

    private int solve(int[] cost, int i) {
        // Base case: If we are at or past the top, no more cost is incurred.
        if (i >= cost.length) {
            return 0;
        }

        // Cost from current step is cost[i] plus the minimum cost from the next two steps.
        int costFromThisStep = cost[i] + Math.min(solve(cost, i + 1), solve(cost, i + 2));
        
        return costFromThisStep;
    }
}
```
### Algorithm
1. Define a recursive function, let's call it `solve(i)`, which calculates the minimum cost to reach the top of the staircase starting from step `i`.
2. The base case for the recursion is when `i` is greater than or equal to `n` (the number of stairs). In this scenario, we are at or past the top, so the cost to proceed is 0.
3. For any other step `i`, the cost is `cost[i]` (the cost to step on stair `i`) plus the minimum of the costs from the next two possible steps: `solve(i+1)` and `solve(i+2)`. The recurrence relation is: `solve(i) = cost[i] + min(solve(i+1), solve(i+2))`.
4. The problem states we can start at either step 0 or step 1. Therefore, the final answer is the minimum of the costs calculated by starting from these two positions: `min(solve(0), solve(1))`.

## Top-Down Dynamic Programming with Memoization
This approach, also known as memoization, is a top-down dynamic programming technique. It optimizes the brute-force recursion by caching the results of subproblems. We use an array, often called a `memo` table, to store the minimum cost calculated for each step. When the function is called for a step, it first checks if the result is already in the table. If so, it returns the cached value; otherwise, it computes the result, stores it in the table, and then returns it. This ensures that each subproblem is solved only once.
**Time:** O(n) - Each subproblem `solve(i)` for `i` from 0 to `n-1` is computed only once. The computation for each state takes constant time. · **Space:** O(n) - We use an array of size `n` for memoization, and the recursion stack can also go up to depth `n`.
**Pros:** Drastically improves time complexity to linear.; Guarantees that each subproblem is solved only once.; Maintains the logical flow of a top-down recursive solution.
**Cons:** Uses O(n) extra space for the memoization table and the recursion stack.; Can be slightly slower than the iterative bottom-up approach due to function call overhead.; May cause a stack overflow for very large `n` (though not an issue with the given constraints).
### Explanation
By adding a memoization table, we avoid the redundant computations that plagued the brute-force approach. Each state `solve(i)` is computed exactly once. The first time `solve(i)` is called, its result is calculated and stored. Subsequent calls for the same `i` will retrieve the result in O(1) time from the memo table, drastically reducing the overall time complexity from exponential to linear.

```java
import java.util.Arrays;

class Solution {
    private int[] memo;

    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        memo = new int[n];
        Arrays.fill(memo, -1); // Initialize memo table with -1
        return Math.min(solve(cost, 0), solve(cost, 1));
    }

    private int solve(int[] cost, int i) {
        if (i >= cost.length) {
            return 0;
        }
        // If result is already computed, return it from memo table.
        if (memo[i] != -1) {
            return memo[i];
        }

        // Compute, store, and return the result.
        memo[i] = cost[i] + Math.min(solve(cost, i + 1), solve(cost, i + 2));
        return memo[i];
    }
}
```
### Algorithm
1. Use the same recursive structure as the brute-force approach.
2. Create a memoization array, `memo`, of size `n` (or `n+1`) to store the computed results for each step. Initialize this array with a special value (e.g., -1) to indicate that the subproblem has not been solved yet.
3. In the recursive function `solve(i)`, before any computation, check if `memo[i]` already contains a valid result. If it does, return the stored value immediately.
4. If `memo[i]` has not been computed, calculate the result using the recurrence: `cost[i] + min(solve(i+1), solve(i+2))`.
5. Store this newly computed result in `memo[i]` before returning it.
6. The initial call remains `min(solve(0), solve(1))`.

## Bottom-Up Dynamic Programming with an Array
This is a bottom-up dynamic programming approach. Instead of starting from the top and recurring down, we build the solution from the bottom (the start of the staircase) up to the top. We use a `dp` array where `dp[i]` stores the minimum cost to reach step `i`. We can calculate `dp[i]` based on the values of previous steps (`dp[i-1]` and `dp[i-2]`), effectively building the solution iteratively. This approach avoids recursion and its associated overhead.
**Time:** O(n) - We iterate through the costs once in a single loop. · **Space:** O(n) - An array of size `n + 1` is used to store the DP values.
**Pros:** Efficient with O(n) time complexity.; Avoids recursion overhead, making it generally faster in practice than memoization.; The iterative logic can be very clear and easy to debug.
**Cons:** Uses O(n) space for the DP array, which is not optimal.
### Explanation
The key insight for this DP formulation is to define `dp[i]` as the minimum cost to reach step `i`. The final destination is the 'top floor', which we can consider as step `n`. To reach any step `i`, we must have come from either step `i-1` or `i-2`. The cost to get to step `i` would be the cost to get to the previous step plus the cost of that previous step. By iterating from the base cases (`dp[0]=0`, `dp[1]=0`), we can fill the `dp` table up to `dp[n]`, which gives us the final answer.

```java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n == 0) return 0;
        if (n == 1) return cost[0];

        int[] dp = new int[n + 1];
        // Base cases: cost to reach step 0 and 1 is 0, as we can start there.
        dp[0] = 0;
        dp[1] = 0;

        // Build up the dp table.
        for (int i = 2; i <= n; i++) {
            // Cost to reach step i is the minimum of coming from i-1 or i-2.
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
}
```
### Algorithm
1. Define a `dp` array of size `n + 1`, where `dp[i]` represents the minimum cost to reach step `i`.
2. The 'top' of the staircase is considered step `n`. Our goal is to find `dp[n]`.
3. Since we can start at step 0 or step 1 without any preceding cost, we can establish base cases. A clever way to model this is to say the cost to reach the 'floor' before step 0 and step 1 is zero. So, `dp[0] = 0` and `dp[1] = 0`.
4. Iterate from `i = 2` up to `n`. In each iteration, calculate `dp[i]` using the recurrence relation: `dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`. This means the cost to reach step `i` is the minimum of two possibilities: coming from step `i-1` (and paying `cost[i-1]`) or coming from step `i-2` (and paying `cost[i-2]`).
5. After the loop completes, `dp[n]` will hold the minimum cost to reach the top.

## Bottom-Up Dynamic Programming with Constant Space
This is the most optimized approach, building upon the bottom-up DP solution. We observe that the calculation for the current step's minimum cost only depends on the costs of the two immediately preceding steps. This means we don't need to store the entire DP table. We can use just two variables to keep track of the necessary previous results. As we iterate, we update these two variables, effectively sliding our window of calculation forward. This reduces the space complexity to constant, O(1), while maintaining the linear time complexity.
**Time:** O(n) - We iterate through the costs once in a single loop. · **Space:** O(1) - We only use a few constant variables to store the state, regardless of the input size.
**Pros:** Optimal space complexity of O(1).; Optimal time complexity of O(n).; Highly efficient and practical for large inputs.
**Cons:** The logic with shifting variables might be slightly less intuitive at first glance compared to using a DP array.
### Explanation
We can think of this as a space-optimized version of the Fibonacci sequence calculation. We only need two previous values to compute the next one. We initialize two variables, `two_steps_back_cost` and `one_step_back_cost`, to represent the costs to reach the first two positions (which is 0). Then, we loop from the third position (`i=2`) to the end. In each step, we calculate the `current_cost` using the two variables, and then update them for the next iteration. This eliminates the need for an O(n) array, making it the most memory-efficient solution.

```java
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        
        // two_steps_back_cost represents the min cost to reach step i-2
        int two_steps_back_cost = 0;
        // one_step_back_cost represents the min cost to reach step i-1
        int one_step_back_cost = 0;

        for (int i = 2; i <= n; i++) {
            int current_cost = Math.min(one_step_back_cost + cost[i - 1], two_steps_back_cost + cost[i - 2]);
            two_steps_back_cost = one_step_back_cost;
            one_step_back_cost = current_cost;
        }

        return one_step_back_cost;
    }
}
```
### Algorithm
1. This approach optimizes the space of the bottom-up DP solution.
2. Notice that to calculate `dp[i]`, we only need `dp[i-1]` and `dp[i-2]`. We don't need the entire `dp` array.
3. Initialize two variables to track the costs for the last two steps. Let `two_steps_back_cost = 0` (representing `dp[0]`) and `one_step_back_cost = 0` (representing `dp[1]`).
4. Iterate from `i = 2` up to `n`.
5. In each iteration, calculate the `current_cost` to reach step `i`: `current_cost = min(one_step_back_cost + cost[i-1], two_steps_back_cost + cost[i-2])`.
6. Update the variables for the next iteration: `two_steps_back_cost` takes the value of `one_step_back_cost`, and `one_step_back_cost` takes the value of `current_cost`.
7. After the loop, `one_step_back_cost` will hold the value of `dp[n]`, which is the final answer.

# Solutions
### Java

```java
class Solution {
public
  int minCostClimbingStairs(int[] cost) {
    int f = 0, g = 0;
    for (int i = 2; i <= cost.length; ++i) {
      int gg = Math.min(f + cost[i - 2], g + cost[i - 1]);
      f = g;
      g = gg;
    }
    return g;
  }
}

```

### JavaScript

```javascript
function minCostClimbingStairs ( cost ) { const n = cost . length ; const f = Array ( n ). fill ( - 1 ); const dfs = i => { if ( i >= n ) { return 0 ; } if ( f [ i ] < 0 ) { f [ i ] = cost [ i ] + Math . min ( dfs ( i + 1 ), dfs ( i + 2 )); } return f [ i ]; }; return Math . min ( dfs ( 0 ), dfs ( 1 )); }
```

### CPP

```cpp
class Solution {
public:
  int minCostClimbingStairs(vector<int> &cost) {
    int f = 0, g = 0;
    for (int i = 2; i <= cost.size(); ++i) {
      int gg = min(f + cost[i - 2], g + cost[i - 1]);
      f = g;
      g = gg;
    }
    return g;
  }
};

```

### Python

```python
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int: f = g = 0 for i in range(2, len(cost) + 1): f, g = g, min(f + cost[i - 2], g + cost[i - 1]) return g

```