# LC 746. Min Cost Climbing Stairs

### [Problem link](https://leetcode.com/problems/min-cost-climbing-stairs/)

###### tags: `leedcode` `python` `c++` `easy` `DP`

You are given an integer array <code>cost</code> where <code>cost[i]</code> is the cost of <code>i^th</code> 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 <code>0</code>, or the step with index <code>1</code>.

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:**

- <code>2 <= cost.length <= 1000</code>
- <code>0 <= cost[i] <= 999</code>

## Solution 1 - DP
#### Python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)

        for i in range(2, len(cost) + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        return dp[-1]

#### C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1, 0);

        for (int i = 2; i < n + 1; i++) {
            dp[i] = min(dp[i- 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp.back();
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        
        vector<int> cache(n + 1, -1);
        function<int(int)> dfs = [&](int i) {
            if (i <= 1) {
                return 0;
            }
            if (cache[i] != -1) {
                return cache[i];
            }
            cache[i] = min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2]);
            return cache[i];
        };
        return dfs(n);
    }
};

## Solution 2 - DP
#### Python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0, 0]

        for i in range(2, len(cost) + 1):
            dp[0], dp[1] = dp[1], min(dp[0] + cost[i - 2], dp[1] + cost[i - 1])

        return dp[1]

#### C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(2, 0);

        for (int i = 2; i < n + 1; i++) {
            int sum = min(dp[0] + cost[i - 2], dp[1] + cost[i - 1]);
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(1) |

## Note
X