目錄

LeetCode 509. 斐波那契數

70. 爬樓梯

746. 使用最小花費爬樓梯

感想

---

文檔講解：代碼隨想錄

動態規劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態規劃是最有效的。

所以動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區別于貪心，貪心沒有狀態推導，而是從局部直接選最優的。

解題步驟：

1. 確定dp數組（dp table）以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

為什么要先確定遞推公式，然后在考慮初始化呢？因為一些情況是遞推公式決定了dp數組要如何初始化！

做動規的題目，寫代碼之前一定要把狀態轉移在dp數組上的具體情況模擬一遍，心中有數，確定最后推出的是想要的結果。然后再寫代碼，如果代碼沒通過就打印dp數組，看看是不是和自己預先推導的哪里不一樣。

題目類型有：基礎題目、背包問題、打家劫舍、股票問題、子序列問題 五大類

LeetCode 509. 斐波那契數

文檔講解：代碼隨想錄

視頻講解：手把手帶你入門動態規劃 | LeetCode：509.斐波那契數_嗶哩嗶哩_bilibili

狀態：簡單題，做對了，要注意特殊情況的處理，怎么返回

class Solution:def fib(self, n: int) -> int:if n == 0: # 邊界條件return 0if n == 1:return 1dp = [0]*(n+1) # step1：dp數組 dp[i]是第i個斐波那契數的值dp[1] = 1 # step3：dp數組初始化for i in range(2, n+1): # step4：因為要用到前面的狀態，所以遍歷順序從前向后dp[i] = dp[i-1] + dp[i-2] # step2：遞推公式/狀態轉移方程return dp[n]

時間復雜度O(n)

空間復雜度O(n)

當前狀態dp[i]只依賴前面兩個狀態dp[i-1]和dp[i-2]，所以可以不用維護一整個數組，而是3個量就可以了，得到上面程序的精簡版：

class Solution:def fib(self, n: int) -> int:if n <= 1:return ndp = [0]*2dp[1] = 1for i in range(2, n+1):sum = dp[0] + dp[1]dp[0] = dp[1]dp[1] = sumreturn dp[1]

?時間復雜度O(n)

空間復雜度O(1)

70. 爬樓梯

文檔講解：代碼隨想錄

視頻講解：

狀態：去年7月11日做過，一周年了，結果還是不會做。 想dp數組的定義，想了好久，不確定到底該怎么定義，到底是第i走了幾個臺階 or 一共走了多少臺階 or 剩下多少臺階，但最后需要返回的是方法數量，這該咋辦呢？

我的錯誤思路：

        # dp[i]是走完第i個臺階后，一共走了多少臺階# 遞推公式 dp[i] = dp[i-1] + 1或2dp = [0] * n # 每次都走一個臺階，最多n步dp[0] = 1  # 但也有可能是2?if dp[-1] < n:  # 該確定遍歷順序了，怎么遍歷?dp

正確思路是直接考慮每層樓梯的方法數目：

爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。

那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層。

所以到第三層樓梯的狀態可以由第二層樓梯 和 到第一層樓梯狀態推導出來。

動規五部曲：

1. 一維數組?dp[i]： 爬到第i層樓梯，有dp[i]種方法

2.?遞推公式：考慮最后一步走幾個臺階，有兩種情況1或者2。上i-1層樓梯，有dp[i - 1]種方法，那么再跳一個臺階就是dp[i]；上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階就是dp[i]。 所以爬到第i層樓梯，有dp[i] =?dp[i - 1] + dp[i - 2] 種方法。

3. 初始化：從dp數組定義的角度出發，不用考慮dp[0]的初始化，直接dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推

4. 從前向后遍歷

5.?舉例推導dp數組? ? 1? 2? 3? 5? 8? 13?

斐波那契數列：0、1、1、2、3、5、8、13、21、34……

與斐波那契數列后半截一樣的

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return ndp = [0]*(n+1) # 因為python下標從0開始，到n 長度為n+1dp[1] = 1dp[2] = 2for i in range(3,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

注意！一定要注意邊界條件的處理！如果不寫 if n==1: return n 的話，當n = 1時，dp[2] = 2 處就會報錯list out of range。

空間和時間復雜度：O(n)? 此題也可以像上一題一樣優化空間復雜度為O(1)

拓展：這道題目還可以繼續深化，就是一步一個臺階，兩個臺階，三個臺階，直到 m個臺階，有多少種方法爬到n階樓頂。這其實是一個完全背包問題，后面會講。

746. 使用最小花費爬樓梯

文檔講解：代碼隨想錄

視頻講解：

狀態：自己做對了！類比上一題。

動規五部曲：

定義：dp[i]是到達第i個臺階需要支付的最少費用

公式：dp[i] = min((dp[i-1] + cost[i-1]), dp[i-2] + cost[i-2])

初始化：dp[0] = 0? ?dp[1]?= 0? ? ? ?題目中說 “你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯” 也就是相當于 跳到 下標 0 或者 下標 1 是不花費體力的

順序：從前向后

舉例：

cost = [1,100,1,1,1,100,1,1,100,1]

下標? ? ? ? ? 0? ? 1? ? 2? ? 3? ? 4? ? 5? ? 6? ? 7? ? 8? ? 9? ?樓頂

dp數組? ? ? 0? ? ?0? ?1? ? 2? ?2? ? 3? ? 3? ? 4? ? ?4? ? 5? ? 6? ? ?確定dp數組長度為len(cost)+1

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

感想

學習用時：晚上2h + 晚上2h