###### tags: `Leetcode` `easy` `dynamic programming` `python` `c++`

# 746. Min Cost Climbing Stairs

## [題目連結:] https://leetcode.com/problems/min-cost-climbing-stairs/description/

## 題目:
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.

## 解題想法:
* 題目為，
* 每個台階都有個cost，求爬到最頂端的位置(len(cost)+1)的cost最小為多少
* 可以從0 or 1階 開始走:
* 每次能走1 or 2階
* 使用DP:
* dp[i]表示到達第i階的最小cost
* dp[i]=min(dp[i-1],dp[i-2])+cost[i] if i>1
* 最頂端可由 最後一階or 倒數第二階 到達:
* return min(dp[-1],dp[-2])

## Python:

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        n=len(cost)
        dp=[0 for _ in range(n)]
        dp[0]=cost[0]
        dp[1]=cost[1]
        for i in range(2,n):
            dp[i]=min(dp[i-1],dp[i-2])+cost[i]
        return min(dp[-1],dp[-2])

if __name__=='__main__':
    result=Solution()
    ans=result.minCostClimbingStairs(cost = [1,100,1,1,1,100,1,1,100,1])
    print(ans) #6

## C++:

#include<iostream>
#include<vector>
using namespace std;

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

int main(){
    vector<int> cost{10,15,20};
    Solution res;
    int ans=res.minCostClimbingStairs(cost);
    cout<<ans<<endl; //15
    return 0;
}