🙉飯不食，水不飲，題必須刷🙉
還不會C語言，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？上簡單題！ 🧡《C語言入門100例》🧡
LeetCode 太簡單？大神盤他！ 🌌《夜深人靜寫演算法》🌌

一、題目

1、題目描述

??陣列的每個下標作為一個階梯，第 i i i 個階梯對應著一個非負數的體力花費值 c o s t [ i ] cost[i] cost[i]（下標從 0 開始），每當爬上一個階梯，都要花費對應的體力值，一旦支付了相應的體力值，就可以選擇 向上爬一個階梯 或者 爬兩個階梯，求找出達到樓層頂部的最低花費，在開始時，可以選擇從下標為 0 或 1 的元素作為初始階梯，
??樣例輸入： c o s t = [ 1 , 99 , 1 , 1 , 1 , 99 , 1 , 1 , 99 , 1 ] cost = [1, 99, 1, 1, 1, 99, 1, 1, 99, 1] cost=[1,99,1,1,1,99,1,1,99,1]
??樣例輸出： 6 6 6
如圖所以，藍色的代表消耗為 1 的樓梯，紅色的代表消耗 99 的樓梯，

2、基礎框架

• c++ 版本給出的基礎框架代碼如下：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    }
};

3、原題鏈接

LeetCode 746. 使用最小花費爬樓梯

二、解題報告

1、思路分析

• 令走到第 i i i 層的最小消耗為 f [ i ] f[i] f[i]
• 假設當前的位置在 i i i 層樓梯，那么只可能從 i ? 1 i-1 i?1 層過來，或者 i ? 2 i-2 i?2 層過來；
• 如果從 i ? 1 i-1 i?1 層過來，則需要消耗體力值： f [ i ? 1 ] + c o s t [ i ? 1 ] f[i-1] + cost[i-1] f[i?1]+cost[i?1]；
• 如果從 i ? 2 i-2 i?2 層過來，則需要消耗體力值： f [ i ? 2 ] + c o s t [ i ? 2 ] f[i-2] + cost[i-2] f[i?2]+cost[i?2]；
• 起點可以在第 0 或者 第 1 層，于是有狀態轉移方程：
• f [ i ] = { 0 i = 0 , 1 min ? ( f [ i ? 1 ] + c o s t [ i ? 1 ] , f [ i ? 2 ] + c o s t [ i ? 2 ] ) i > 1 f[i] = \begin{cases} 0 & i=0,1\\ \min ( f[i-1] + cost[i-1], f[i-2] + cost[i-2] ) & i > 1\end{cases} f[i]={0min(f[i?1]+cost[i?1],f[i?2]+cost[i?2])?i=0,1i>1?
  

2、時間復雜度

• 狀態數： O ( n ) O(n) O(n)
• 狀態轉移： O ( 1 ) O(1) O(1)
• 時間復雜度： O ( n ) O(n) O(n)

3、代碼詳解

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

• ( 1 ) (1) (1) 用f[i]代表到達第 i i i 層的消耗的最小體力值，
• ( 2 ) (2) (2) 初始化；
• ( 3 ) (3) (3) 狀態轉移；

三、本題小知識

有沒有發現，這個問題和斐波那契數列很像，只不過斐波那契數列是求和，這里是求最小值，