Solution: Min Cost Climbing Stairs
Tags: algorithms, javascript, java, python
Published: 2021-06-07 07:37:44

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/min-cost-climbing-stairs/discuss/1256642).*

---

#### [Leetcode Problem #746 (*Easy*): Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
You are given an integer array `cost` where `cost[i]` is the cost of `i`th 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_.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| cost = [10,15,20]
Output:| 15
Explanation:| Cheapest is: start on cost[1], pay that cost, and go to the top.
>
Example 2:||
|---:|---|
Input:| cost = [1,100,1,1,1,100,1,1,100,1]
Output:| 6
Explanation:| Cheapest is: start on cost[0], and only step on 1s, skipping cost[3].

---

#### ***Constraints:***
>
 - `2 <= cost.length <= 1000`
 - `0 <= cost[i] <= 999`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

This is an introduction to a **top-down dynamic programming** (**DP**) approach solution. We can think of this as the build-up of a number of smaller subproblems, starting at the end.

At each step, we can consider the answer to be the combined **cost** of the current step, plus the lesser result of the total **cost** of each of the solutions starting at the next two steps. This means that, thinking backwards, we can solve for the smallest problem first, and then build down from there.

For the last two steps, the answer is clearly their individual **cost**. For the third to last step, it's that step's **cost**, plus the lower of the last two steps. Now that we know that, we can store that data for later use at lower steps. Normally, this would call for a DP array, but in this case, we could simply store the values **in-place**.

_(**Note**: If we choose to not modify the input, we could create a DP array to store this information at the expense of **O(N) extra space**.)_

So we should iterate downward from the end, starting at the third step from the end, and update the values in **cost[i]** with the best total **cost** from **cost[i]** to the end. Then, once we reach the bottom of the steps, we can choose the best result of **cost[0]** and **cost[1]** and **return** our answer.

 - _**Time Complexity: O(N)** where **N** is the length of **cost**_
 - _**Space Complexity: O(1)**_
   - _or **O(N)** if we use a separate DP array_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var minCostClimbingStairs = function(cost) {
    for (let i = cost.length - 3; ~i; i--)
        cost[i] += Math.min(cost[i+1], cost[i+2])
    return Math.min(cost[0], cost[1])
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
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])
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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]);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        for (int i = cost.size() - 3; ~i; i--)
            cost[i] += min(cost[i+1], cost[i+2]);
        return min(cost[0], cost[1]);
    }
};
```