leetcode(力扣) 746. 使用最小花費爬樓梯 ( 動态規劃 & 解析詭異題目 )

文章目錄

• ​​題目描述​​
• ​​簡化題目​​
• ​​思路分析​​
• ​​完整代碼​​

題目描述

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個台階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個台階。

你可以選擇從下标為 0 或下标為 1 的台階開始爬樓梯。

請你計算并傳回達到樓梯頂部的最低花費。

示例 1：

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

輸出：15

解釋：你将從下标為 1 的台階開始。

支付 15 ，向上爬兩個台階，到達樓梯頂部。

總花費為 15 。

示例 2：

輸入：cost = [1,100,1,1,1,100,1,1,100,1]

輸出：6

解釋：你将從下标為 0 的台階開始。

• 支付 1 ，向上爬兩個台階，到達下标為 2 的台階。
• 支付 1 ，向上爬兩個台階，到達下标為 4 的台階。
• 支付 1 ，向上爬兩個台階，到達下标為 6 的台階。
• 支付 1 ，向上爬一個台階，到達下标為 7 的台階。
• 支付 1 ，向上爬兩個台階，到達下标為 9 的台階。

• 支付 1 ，向上爬一個台階，到達樓梯頂部。

  總花費為 6 。

簡化題目

這題目描述的就很詭異。理清楚花費順序比寫出代碼要難哈哈。

簡單來說，cost = [10,15,20] 題目給了這個數組，樓頂在最後 cost = [10,15,20] X。

也就是我标的X的地方是樓頂，可以從0号或者1号位置開始，每次可以選擇走1步或者2步，走的時候要花費目前數值的體力。

這裡何時花費體力值比較繞，總的來說，第一步必花費體力值，後面到哪裡就直接花掉。

順序步驟：

即 第一步花費 -> 選擇走幾步 -> 到達某個點(直接花費掉該點的體力值)->繼續選擇走幾步 -> 到達某個點(繼續花體力)

且最後一步到達頂點的台階不需要花費體力 這點很重要

比如cost = [10,15,20] 從1号位置開始走兩步，直接能達到X的位置，花費15。為最小花費。

思路分析

動态規劃五步走：

1.确定dp[i]含義;

dp[i] 表示到達第i個台階所要花費的最小體力值。

2.确定遞推公式：

到達第i個台階隻能從i-1邁一步上來，或者從i-2邁兩步上來。顯然選擇花費最小的方案走。

得到遞推公式：

dp[i] = min(dp[i-1],dp[i-2]) + cost[i]。

這裡為啥要加上cost[i],，因為題目中說了：每當你爬上一個階梯你都要花費對應的體力值

3.初始化dp數組;

根據上面的遞推公式，要初始化前兩個。

dp[0] = cost[0]

dp[1] = cost[1]

4.确定周遊順序：

由遞推公式可知：

第一個和第二個确定第三個。是以正向周遊。

5.模拟dp看結果：

用示例2，cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]：

相應dp數組：[1, 100, 2, 3, 3, 103, 4, 5, 104, 6]

完整代碼

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[-1],dp[-2])