---
tags: LeetCode
---

# 746. Min Cost Climbing Stairs
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

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

Note:
cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

輸入範本如下

public class Solution {
        public int MinCostClimbingStairs(int[] cost)
        {
        }
}

### 直覺想法
[70. Climbing Stairs](https://hackmd.io/OqEJiweDQOOIzuTlEMrKYg?view) 的變化題 ,
此題最難的是把遞迴式寫出來. 如果寫得出來 , 應該沒大問題.

1. dp[i] 代表到達第 i 階時的最小成本
- dp[i] = Min( dp[i- 2] + cost[i - 2] , dp[i - 1] + cost[i - 1] )

    92 ms	25.7 MB
    You are here!
    Your runtime beats 85.53 % of csharp submissions.
    public int MinCostClimbingStairs(int[] cost)
    {
        int n0 = 0, n1 = 0;
        for (int i = 2; i <= cost.Length; i++)
        {
            int temp = Math.Min(cost[i - 2] + n0, cost[i - 1] + n1);
            n0 = n1;
            n1 = temp;
        }
        return n1;
    }

2. dp[i] 代表要從第 i 階離開時的最小成本.
- dp[i] = cost[i] + min(dp[i- 1], dp[i - 2])

    92 ms	25.8 MB
    You are here!
    Your runtime beats 85.53 % of csharp submissions.
    public int MinCostClimbingStairs(int[] cost)
    {
        int n0 = cost[0], n1 = cost[1];
        for (int i = 2; i < cost.Length; i++)
        {
            int temp = cost[i] + Math.Min(n0, n1);
            n0 = n1;
            n1 = temp;
        }
        return Math.Min(n0, n1);
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: