理論基礎

視頻講解

什么是動態規劃

如果某一問題有很多重疊子問題，使用動態規劃是最有效的，所以動態規劃中每一個狀態一定是由上一個狀態推導出來的，這一點就區分于貪心，貪心沒有狀態推導，而是從局部直接選最優的，例如：有N件物品和一個最多能背重量為W 的背包，第i件物品的重量是weight[i]，得到的價值是value[i]，每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大，動態規劃中dp[j]是由dp[j-weight[i]]推導出來的，然后取max(dp[j], dp[j - weight[i]] + value[i])，但如果是貪心呢，每次拿物品選一個最大的或者最小的就完事了，和上一個狀態沒有關系，所以貪心解決不了動態規劃的問題其實大家也不用死扣動規和貪心的理論區別，后面做做題目自然就知道了，而且很多講解動態規劃的文章都會講最優子結構啊和重疊子問題啊這些，這些東西都是教科書的上定義，晦澀難懂而且不實用，大家知道動規是由前一個狀態推導出來的，而貪心是局部直接選最優的，對于刷題來說就夠用了，上述提到的背包問題，后序會詳細講解

動態規劃的解題步驟

對于動態規劃問題，我將拆解為如下五步曲，這五步都搞清楚了，才能說把動態規劃真的掌握了！

1. 確定dp數組以及下標的含義
2. 確定遞推公式
3. dp數組如何初始化
4. 確定遍歷順序
5. 舉例推導dp數組

動態規劃應該如何debug

找問題的最好方式就是把dp數組打印出來，看看究竟是不是按照自己思路推導的！做動規的題目，寫代碼之前一定要把狀態轉移在dp數組的上具體情況模擬一遍，心中有數，確定最后推出的是想要的結果

509. 斐波那契數

題目鏈接
視頻講解
斐波那契數 （通常用 F(n) 表示）形成的序列稱為 斐波那契數列，該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和，也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
給定 n ，請計算 F(n)

輸入：n = 4
輸出：3

動規五部曲：
這里我們要用一個一維dp數組來保存遞歸的結果，確定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 {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}
};

當然可以發現，我們只需要維護兩個數值就可以了，不需要記錄整個序列
代碼如下：

class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

遞歸解法

class Solution {
public:int fib(int N) {if (N < 2) return N;return fib(N - 1) + fib(N - 2);}
};

70. 爬樓梯

題目鏈接
視頻講解
假設你正在爬樓梯，需要 n 階你才能到達樓頂，每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

輸入：n = 3
輸出：3

本題如果沒有接觸過的話，會感覺比較難，多舉幾個例子，就可以發現其規律，爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法，那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層，所以到第三層樓梯的狀態可以由第二層樓梯 和 到第一層樓梯狀態推導出來，那么就可以想到動態規劃了
我們來分析一下，動規五部曲：
定義一個一維數組來記錄不同樓層的狀態
1.確定dp數組以及下標的含義
dp[i]： 爬到第i層樓梯，有dp[i]種方法
2.確定遞推公式
如何可以推出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[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏這體現出確定dp數組以及下標的含義的重要性！
3.dp數組如何初始化
再回顧一下dp[i]的定義：爬到第i層樓梯，有dp[i]種方法，那么i為0，dp[i]應該是多少呢，這個可以有很多解釋，但基本都是直接奔著答案去解釋的，例如強行安慰自己爬到第0層，也有一種方法，什么都不做也就是一種方法即：dp[0] = 1，相當于直接站在樓頂，但總有點牽強的成分，那還這么理解呢：我就認為跑到第0層，方法就是0啊，一步只能走一個臺階或者兩個臺階，然而樓層是0，直接站樓頂上了，就是不用方法，dp[0]就應該是0.其實這么爭論下去沒有意義，大部分解釋說dp[0]應該為1的理由其實是因為dp[0]=1的話在遞推的過程中i從2開始遍歷本題就能過，然后就往結果上靠去解釋dp[0] = 1，從dp數組定義的角度上來說，dp[0] = 0 也能說得通，需要注意的是：題目中說了n是一個正整數，題目根本就沒說n有為0的情況，所以本題其實就不應該討論dp[0]的初始化！我相信dp[1] = 1，dp[2] = 2，這個初始化大家應該都沒有爭議的，所以我的原則是：不考慮dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推，這樣才符合dp[i]的定義
4.確定遍歷順序
從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的
5.舉例推導dp數組
舉例當n為5的時候，dp table（dp數組）應該是這樣的

如果代碼出問題了，就把dp table 打印出來，看看究竟是不是和自己推導的一樣，此時大家應該發現了，這不就是斐波那契數列么！唯一的區別是，沒有討論dp[0]應該是什么，因為dp[0]在本題沒有意義

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因為下面直接對dp[2]操作了，防止空指針vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是從3開始的dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

746. 使用最小花費爬樓梯

題目鏈接
視頻講解
給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用，一旦你支付此費用，即可選擇向上爬一個或者兩個臺階，你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯，請你計算并返回達到樓梯頂部的最低花費

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

1.確定dp數組以及下標的含義
使用動態規劃，就要有一個數組來記錄狀態，本題只需要一個一維數組dp[i]就可以了，dp[i]的定義：到達第i臺階所花費的最少體力為dp[i]，對于dp數組的定義，一定要清晰！
2.確定遞推公式
可以有兩個途徑得到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]);
3.dp數組如何初始化
看一下遞歸公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就夠了，其他的最終都是dp[0]dp[1]推出，那么 dp[0] 應該是多少呢？ 根據dp數組的定義，到達第0臺階所花費的最小體力為dp[0]，那么有同學可能想，那dp[0] 應該是 cost[0]，例如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 的話，dp[0] 就是 cost[0] 應該是1，這里就要說明本題力扣為什么改題意，而且修改題意之后 就清晰很多的原因了，新題目描述中明確說了 “你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。” 也就是說 到達 第 0 個臺階是不花費的，但從 第0 個臺階 往上跳的話，需要花費 cost[0]，所以初始化 dp[0] = 0，dp[1] = 0;
4.確定遍歷順序
最后一步，遞歸公式有了，初始化有了，如何遍歷呢？本題的遍歷順序其實比較簡單，簡單到都忽略了思考這一步直接就把代碼寫出來了，因為是模擬臺階，而且dp[i]由dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數組就可以了，但是稍稍有點難度的動態規劃，其遍歷順序并不容易確定下來。 例如：01背包，都知道兩個for循環，一個for遍歷物品嵌套一個for遍歷背包容量，那么為什么不是一個for遍歷背包容量嵌套一個for遍歷物品呢？ 以及在使用一維dp數組的時候遍歷背包容量為什么要倒序呢？這些都與遍歷順序息息相關
5.舉例推導dp數組
拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，來模擬一下dp數組的狀態變化，如下

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0; // 默認第一步都是不花費體力的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()];}
};