# [LeetCode 746. Min Cost Climbing Stairs ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3770/)
### Daily challenge Jun 7, 2021 (EASY)

>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.

:::info
**Example 1:**
**Input:** cost = [10,15,20]
**Output:** 15
**Explanation:** Cheapest is: start on cost[1], pay that cost, and go to the top.
:::

:::info
**Example 1:**
**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].
:::

:::warning
**Constraints:**
* 2 <= cost.length <= 1000
* 0 <= cost[i] <= 999
:::

---

### Approach 1 : DP :bulb:
**`4 ms ( 94.32% )`** **`O()`**

初始位置可以在 **`index 0 or 1`**，一次可以走 **`1 or 2 steps`**。

所以要走到 `index = i` 的位置只能從 `index = ( i - 1 ) or index = ( i - 2 )`，
那我們只需要從低樓層開始判斷到頂樓，找出走道每層樓所需的 `minimum cost` 即可。
> Initial state : `dp[0] = 0, dp[1] = 0`。
> ---> **`dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`**。

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