????????今天開始動態規劃的部分！
? ? ? ? 其實說白了，動態規劃我感覺就是找類似遞歸的規律，
動態規劃理論基礎
????????動態規劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態規劃是最有效的。
????????所以動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分于貪心，貪心沒有狀態推導，而是從局部直接選最優的
????????對于動態規劃問題，我將拆解為如下五步曲，這五步都搞清楚了，才能說把動態規劃真的掌握了！
- 確定dp數組（dp table）以及下標的含義
- 確定遞推公式
- dp數組如何初始化
- 確定遍歷順序
- 舉例推導dp數組（過程模擬）
509. 斐波那契數
- 確定dp數組以及下標的含義
????????dp[i]的定義為：第i個數的斐波那契數值是dp[i]
- 確定遞推公式
????????題目已經把遞推公式直接給我們了：狀態轉移方程 dp[i] = dp[i - 1] + dp[i - 2];
- dp數組如何初始化
????????題目中把如何初始化也直接給我們了，如下：
dp[0] = 0;
dp[1] = 1;- 確定遍歷順序
????????從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的
- 舉例推導dp數組（后續省略）
????????按照這個遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來推導一下，當N為10的時候，dp數組應該是如下的數列：
????????0 1 1 2 3 5 8 13 21 34 55
????????如果代碼寫出來，發現結果不對，就把dp數組打印出來看看和我們推導的數列是不是一致的。
class Solution:def fib(self, n: int) -> int:if n == 0:return 0dp = [0] * (n + 1)dp[0] = 0dp[1] = 1 # 初始值for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2] # 遞推公式return dp[n]'''
class Solution:def fib(self, n: int) -> int:if n <= 1:return nprev1, prev2 = 0, 1for _ in range(2, n + 1):curr = prev1 + prev2prev1, prev2 = prev2, currreturn prev2
'''
遞歸實現
class Solution:def fib(self, n: int) -> int:if n < 2:return nreturn self.fib(n - 1) + self.fib(n - 2)70. 爬樓梯
????????提取信息并轉化：爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。
- 確定dp數組以及下標的含義
????????dp[i]： 爬到第i層樓梯，有dp[i]種方法
- 確定遞推公式
????????如何可以推出dp[i]呢？從dp[i]的定義可以看出，dp[i] 可以有兩個方向推出來。
????????首先是dp[i - 1]，上i-1層樓梯，有dp[i - 1]種方法，那么再一步跳一個臺階不就是dp[i]了么。還有就是dp[i - 2]，上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階不就是dp[i]了么。那么dp[i]就是 dp[i - 1]與dp[i - 2]之和！
????????所以dp[i] = dp[i - 1] + dp[i - 2] 。
- dp數組如何初始化
????????dp[1] = 1，dp[2] = 2，這個初始化很容易可以得出。
- 確定遍歷順序
????????從遞推公式dp[i] = dp[i - 1] + dp[i - 2]中可以看出，遍歷順序一定是從前向后遍歷的，這個題目的解法和上個題目幾乎一樣！
class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[1] = 1dp[2] = 2 # 初始值for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2] # 遞推公式return dp[n]746. 使用最小花費爬樓梯
- 確定dp數組以及下標的含義
????????使用動態規劃，就要有一個數組來記錄狀態，本題只需要一個一維數組dp[i]就可以了。
????????dp[i]的定義：到達第i臺階所花費的最少體力為dp[i]。
- 確定遞推公式
????????可以有兩個途徑得到dp[i]，一個是dp[i-1] 一個是dp[i-2]。
- dp[i - 1] 跳到 dp[i] 需要花費 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp[i] 需要花費 dp[i - 2] + cost[i - 2]。
????????那么究竟是選從dp[i - 1]跳還是從dp[i - 2]跳呢？一定是選最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
- dp數組如何初始化
????????初始化 dp[0] = 0，dp[1] = 0;
- 確定遍歷順序
????????從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的
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):dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]
)