數(shù)據(jù)結(jié)構(gòu)與算法之使用最小花費(fèi)爬樓梯
使用最小花費(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 開(kāi)始)。
每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯。
請(qǐng)你找出達(dá)到樓層頂部的最低花費(fèi)。在開(kāi)始時(shí)，你可以選擇從下標(biāo)為 0 或 1 的元素作為初始階梯。
示例 1：
- 輸入：cost = [10, 15, 20]
- 輸出：15
- 解釋：最低花費(fèi)是從 cost[1] 開(kāi)始，然后走兩步即可到階梯頂，一共花費(fèi) 15 。
示例 2：
- 輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
- 輸出：6
- 解釋：最低花費(fèi)方式是從 cost[0] 開(kāi)始，逐個(gè)經(jīng)過(guò)那些 1 ，跳過(guò) cost[3] ，一共花費(fèi) 6 。
提示：
- cost 的長(zhǎng)度范圍是 [2, 1000]。
- cost[i] 將會(huì)是一個(gè)整型數(shù)據(jù)，范圍為 [0, 999] 。
思路
這道題目可以說(shuō)是昨天動(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ù)組來(lái)記錄狀態(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)轭}目中說(shuō)了：每當(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é)都忽略了思考這一步直接就把代碼寫(xiě)出來(lái)了。
因?yàn)槭悄M臺(tái)階，而且dp[i]又dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數(shù)組就可以了。
但是稍稍有點(diǎn)難度的動(dòng)態(tài)規(guī)劃，其遍歷順序并不容易確定下來(lái)。
例如：01背包，都知道兩個(gè)for循環(huán)，一個(gè)for遍歷物品嵌套一個(gè)for遍歷背包容量，那么為什么不是一個(gè)for遍歷背包容量嵌套一個(gè)for遍歷物品呢?以及在使用一維dp數(shù)組的時(shí)候遍歷背包容量為什么要倒敘呢?
這些都是遍歷順序息息相關(guān)。當(dāng)然背包問(wèn)題后續(xù)「代碼隨想錄」都會(huì)重點(diǎn)講解的!
舉例推導(dǎo)dp數(shù)組
拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，來(lái)模擬一下dp數(shù)組的狀態(tài)變化，如下：
使用最小花費(fèi)爬樓梯
如果大家代碼寫(xiě)出來(lái)有問(wèn)題，就把dp數(shù)組打印出來(lái)，看看和如上推導(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]就是由前兩位推出來(lá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)然我不建議這么寫(xiě)，能寫(xiě)出版本一就可以了，直觀簡(jiǎn)潔!
在后序的講解中，可能我會(huì)忽略這種版本二的寫(xiě)法，大家只要知道有這么個(gè)寫(xiě)法就可以了哈。
拓展
這道題描述也確實(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è)人理解：題意說(shuō)的其實(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)體力的。
所以代碼這么寫(xiě)：
- 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()];
- }
- };
這么寫(xiě)看上去比較順，但是就是感覺(jué)和題目描述的不太符。哈哈，也沒(méi)有必要這么細(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è)系列開(kāi)始的時(shí)候，都有錄友和我反饋說(shuō)題目太簡(jiǎn)單了，趕緊上難度，但也有錄友和我說(shuō)有點(diǎn)難了，快跟不上了。
其實(shí)我選的題目都是有目的性的，就算是簡(jiǎn)單題，也是為了練習(xí)方法論，然后難度都是梯度上來(lái)的，一環(huán)扣一環(huán)。
但我也可以隨便選來(lái)一道難題講唄，這其實(shí)是最省事的，不用管什么題目順序，看心情找一道就講。
難的是把題目按梯度排好，循序漸進(jìn)，再按照統(tǒng)一方法論把這些都串起來(lái)，哈哈，所以大家不要催我哈，按照我的節(jié)奏一步一步來(lái)就行啦。
學(xué)算法，認(rèn)準(zhǔn)「代碼隨想錄」，沒(méi)毛病!
其他語(yǔ)言版本
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])
- };
