理論基礎
動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分于貪心，貪心沒有狀態推導，而是從局部直接選最優的
動態規劃的解題步驟
- 確定dp數組（dp table）以及下標的含義
- 確定遞推公式
- dp數組如何初始化
- 確定遍歷順序
- 舉例推導dp數組
動態規劃應該如何debug？
? ? ? 找問題的最好方式就是把dp數組打印出來，看看究竟是不是按照自己思路推導的！
509. 斐波那契數
- 確定dp數組以及下標的含義：dp[i]的定義為：第i個數的斐波那契數值是dp[i]
- 確定遞推公式：dp[i] = dp[i - 1] + dp[i - 2]
- dp數組如何初始化：dp[0] = 0 dp[1] = 1
- 確定遍歷順序：從前向后
- 舉例推導dp數組
class Solution:def fib(self, n: int) -> int:if n <= 1:return ndp = [0, 1]for i in range(2, n+1):total = dp[0] + dp[1]dp[0] = dp[1]dp[1] = totalreturn dp[1]70. 爬樓梯
- 確定dp數組以及下標的含義：dp[i]為爬上i階樓梯有多少方法
- 確定遞推公式：dp[i] = dp[i-1] + dp[i-2]
- dp數組如何初始化：dp[1] = 1 dp[2] = 2
- 確定遍歷順序：從前向后遍歷
- 舉例推導dp數組
class Solution:def climbStairs(self, n: int) -> int:if n <= 2:return ndp = [1, 2]for i in range(3, n+1):total = dp[0] + dp[1]dp[0] = dp[1]dp[1] = totalreturn dp[1]746. 使用最小花費爬樓梯
- 確定dp數組以及下標的含義：dp[i]代表爬上第i個臺階的最低花費
- 確定遞推公式：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
- dp數組如何初始化：dp[0] = 0 dp[1] = 0
- 確定遍歷順序：從前向后遍歷
- 舉例推導dp數組
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:if len(cost) <= 1:return 0dp = [0, 0]for i in range(2, len(cost)+1):total = min(dp[1]+cost[i-1], dp[0]+cost[i-2])dp[0] = dp[1]dp[1] = totalreturn dp[1]
)
