[[443068]]

使用最小花費(fèi)爬樓梯

力扣題目鏈接：https://leetcode-cn.com/problems/min-cost-climbing-stairs

數(shù)組的每個(gè)下標(biāo)作為一個(gè)階梯，第 i 個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值 cost[i](下標(biāo)從 0 開始)。

每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯。

請(qǐng)你找出達(dá)到樓層頂部的最低花費(fèi)。在開始時(shí)，你可以選擇從下標(biāo)為 0 或 1 的元素作為初始階梯。

示例 1：

• 輸入：cost = [10, 15, 20]
• 輸出：15
• 解釋：最低花費(fèi)是從 cost[1] 開始，然后走兩步即可到階梯頂，一共花費(fèi) 15 。

示例 2：

• 輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
• 輸出：6
• 解釋：最低花費(fèi)方式是從 cost[0] 開始，逐個(gè)經(jīng)過那些 1 ，跳過 cost[3] ，一共花費(fèi) 6 。

提示：

• cost 的長(zhǎng)度范圍是 [2, 1000]。
• cost[i] 將會(huì)是一個(gè)整型數(shù)據(jù)，范圍為 [0, 999] 。

思路

這道題目可以說是昨天動(dòng)態(tài)規(guī)劃：爬樓梯的花費(fèi)版本。

注意題目描述：每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯

所以示例1中只花費(fèi)一個(gè)15 就可以到階梯頂，最后一步可以理解為 不用花費(fèi)。

讀完題大家應(yīng)該知道指定需要?jiǎng)討B(tài)規(guī)劃的，貪心是不可能了。

確定dp數(shù)組以及下標(biāo)的含義

使用動(dòng)態(tài)規(guī)劃，就要有一個(gè)數(shù)組來記錄狀態(tài)，本題只需要一個(gè)一維數(shù)組dp[i]就可以了。

dp[i]的定義：到達(dá)第i個(gè)臺(tái)階所花費(fèi)的最少體力為dp[i]。(注意這里認(rèn)為是第一步一定是要花費(fèi))

對(duì)于dp數(shù)組的定義，大家一定要清晰!

確定遞推公式

可以有兩個(gè)途徑得到dp[i]，一個(gè)是dp[i-1] 一個(gè)是dp[i-2]。

那么究竟是選dp[i-1]還是dp[i-2]呢?

一定是選最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

注意這里為什么是加cost[i]，而不是cost[i-1],cost[i-2]之類的，因?yàn)轭}目中說了：每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值

dp數(shù)組如何初始化

根據(jù)dp數(shù)組的定義，dp數(shù)組初始化其實(shí)是比較難的，因?yàn)椴豢赡艹跏蓟癁榈趇臺(tái)階所花費(fèi)的最少體力。

那么看一下遞歸公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就夠了，其他的最終都是dp[0]dp[1]推出。

所以初始化代碼為：

vector<int> dp(cost.size()); 
dp[0] = cost[0]; 
dp[1] = cost[1]; 

確定遍歷順序

最后一步，遞歸公式有了，初始化有了，如何遍歷呢?

本題的遍歷順序其實(shí)比較簡(jiǎn)單，簡(jiǎn)單到很多同學(xué)都忽略了思考這一步直接就把代碼寫出來了。

因?yàn)槭悄M臺(tái)階，而且dp[i]又dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數(shù)組就可以了。

但是稍稍有點(diǎn)難度的動(dòng)態(tài)規(guī)劃，其遍歷順序并不容易確定下來。

例如：01背包，都知道兩個(gè)for循環(huán)，一個(gè)for遍歷物品嵌套一個(gè)for遍歷背包容量，那么為什么不是一個(gè)for遍歷背包容量嵌套一個(gè)for遍歷物品呢?以及在使用一維dp數(shù)組的時(shí)候遍歷背包容量為什么要倒敘呢?

這些都是遍歷順序息息相關(guān)。當(dāng)然背包問題后續(xù)「代碼隨想錄」都會(huì)重點(diǎn)講解的!

舉例推導(dǎo)dp數(shù)組

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，來模擬一下dp數(shù)組的狀態(tài)變化，如下：

使用最小花費(fèi)爬樓梯

如果大家代碼寫出來有問題，就把dp數(shù)組打印出來，看看和如上推導(dǎo)的是不是一樣的。

以上分析完畢，整體C++代碼如下：

// 版本一 
class Solution { 
public: 
    int minCostClimbingStairs(vector<int>& cost) { 
        vector<int> dp(cost.size()); 
        dp[0] = cost[0]; 
        dp[1] = cost[1]; 
        for (int i = 2; i < cost.size(); i++) { 
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; 
        } 
        // 注意最后一步可以理解為不用花費(fèi)，所以取倒數(shù)第一步，第二步的最少值 
        return min(dp[cost.size() - 1], dp[cost.size() - 2]); 
    } 
}; 

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

還可以優(yōu)化空間復(fù)雜度，因?yàn)閐p[i]就是由前兩位推出來的，那么也不用dp數(shù)組了，C++代碼如下：

// 版本二 
class Solution { 
public: 
    int minCostClimbingStairs(vector<int>& cost) { 
        int dp0 = cost[0]; 
        int dp1 = cost[1]; 
        for (int i = 2; i < cost.size(); i++) { 
            int dpi = min(dp0, dp1) + cost[i]; 
            dp0 = dp1; // 記錄一下前兩位 
            dp1 = dpi; 
        } 
        return min(dp0, dp1); 
    } 
}; 

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

當(dāng)然我不建議這么寫，能寫出版本一就可以了，直觀簡(jiǎn)潔!

在后序的講解中，可能我會(huì)忽略這種版本二的寫法，大家只要知道有這么個(gè)寫法就可以了哈。

拓展

這道題描述也確實(shí)有點(diǎn)魔幻。

題目描述為：每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯。

示例1：

輸入：cost = [10, 15, 20] 輸出：15

從題目描述可以看出：要不是第一步不需要花費(fèi)體力，要不就是第最后一步不需要花費(fèi)體力，我個(gè)人理解：題意說的其實(shí)是第一步是要支付費(fèi)用的!。因?yàn)槭钱?dāng)你爬上一個(gè)臺(tái)階就要花費(fèi)對(duì)應(yīng)的體力值!

所以我定義的dp[i]意思是也是第一步是要花費(fèi)體力的，最后一步不用花費(fèi)體力了，因?yàn)橐呀?jīng)支付了。

當(dāng)然也可以樣，定義dp[i]為:第一步是不花費(fèi)體力，最后一步是花費(fèi)體力的。

所以代碼這么寫：

class Solution { 
public: 
    int minCostClimbingStairs(vector<int>& cost) { 
        vector<int> dp(cost.size() + 1); 
        dp[0] = 0; // 默認(rèn)第一步都是不花費(fèi)體力的 
        dp[1] = 0; 
        for (int i = 2; i <= cost.size(); i++) { 
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); 
        } 
        return dp[cost.size()]; 
    } 
}; 

這么寫看上去比較順，但是就是感覺和題目描述的不太符。哈哈，也沒有必要這么細(xì)扣題意了，大家只要知道，題目的意思反正就是要不是第一步不花費(fèi)，要不是最后一步不花費(fèi)，都可以。

總結(jié)

大家可以發(fā)現(xiàn)這道題目相對(duì)于 昨天的動(dòng)態(tài)規(guī)劃：爬樓梯有難了一點(diǎn)，但整體思路是一樣。

從動(dòng)態(tài)規(guī)劃：斐波那契數(shù)到 動(dòng)態(tài)規(guī)劃：爬樓梯再到今天這道題目，錄友們感受到循序漸進(jìn)的梯度了嘛。

每個(gè)系列開始的時(shí)候，都有錄友和我反饋說題目太簡(jiǎn)單了，趕緊上難度，但也有錄友和我說有點(diǎn)難了，快跟不上了。

其實(shí)我選的題目都是有目的性的，就算是簡(jiǎn)單題，也是為了練習(xí)方法論，然后難度都是梯度上來的，一環(huán)扣一環(huán)。

但我也可以隨便選來一道難題講唄，這其實(shí)是最省事的，不用管什么題目順序，看心情找一道就講。

難的是把題目按梯度排好，循序漸進(jìn)，再按照統(tǒng)一方法論把這些都串起來，哈哈，所以大家不要催我哈，按照我的節(jié)奏一步一步來就行啦。

學(xué)算法，認(rèn)準(zhǔn)「代碼隨想錄」，沒毛病!

其他語言版本

Java

class Solution { 
    public int minCostClimbingStairs(int[] cost) { 
        if (cost == null || cost.length == 0) { 
            return 0; 
        } 
        if (cost.length == 1) { 
            return cost[0]; 
        } 
        int[] dp = new int[cost.length]; 
        dp[0] = cost[0]; 
        dp[1] = cost[1]; 
        for (int i = 2; i < cost.length; i++) { 
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; 
        } 
        //最后一步，如果是由倒數(shù)第二步爬，則最后一步的體力花費(fèi)可以不用算 
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]); 
    } 
} 

Python

class Solution: 
    def minCostClimbingStairs(self, cost: List[int]) -> int: 
        dp = [0] * (len(cost)) 
        dp[0] = cost[0] 
        dp[1] = cost[1] 
        for i in range(2, len(cost)): 
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i] 
        return min(dp[len(cost) - 1], dp[len(cost) - 2]) 

Go

func minCostClimbingStairs(cost []int) int { 
 dp := make([]int, len(cost)) 
 dp[0], dp[1] = cost[0], cost[1] 
 for i := 2; i < len(cost); i++ { 
  dp[i] = min(dp[i-1], dp[i-2]) + cost[i] 
 } 
 return min(dp[len(cost)-1], dp[len(cost)-2]) 
} 
 
func min(a, b int) int { 
 if a < b { 
  return a 
 } 
 return b 
} 

 Javascript

var minCostClimbingStairs = function(cost) { 
    const dp = [ cost[0], cost[1] ] 
 
    for (let i = 2; i < cost.length; ++i) { 
        dp[i] = Math.min(dp[i -1] + cost[i], dp[i - 2] + cost[i]) 
    } 
 
    return Math.min(dp[cost.length - 1], dp[cost.length - 2]) 
};