通知：我已經將刷題指南全部整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上閱讀，這個倉庫每天都會更新，大家快去給一個star支持一下吧！
昨天動態規劃：關於01背包問題，你該了解這些！中是用二維dp數組來講解01背包。
今天我們就來說一說滾動數組，其實在前面的題目中我們已經用到過滾動數組了，就是把二維dp降為一維dp，一些錄友當時還表示比較困惑。
那麼我們通過01背包，來徹底講一講滾動數組！
接下來還是用如下這個例子來進行講解
背包最大重量為4。
物品為：
問背包能背的物品最大價值是多少？
一維dp數組（滾動數組）對於背包問題其實狀態都是可以壓縮的。
在使用二維數組的時候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其實可以發現如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
於其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數組了，只用dp[j]（一維數組，也可以理解是一個滾動數組）。
這就是滾動數組的由來，需要滿足的條件是上一層可以重複利用，直接拷貝到當前層。
讀到這裡估計大家都忘了 dp[i][j]裡的i和j表達的是什麼了，i是物品，j是背包容量。
dp[i][j] 表示從下標為[0-i]的物品裡任意取，放進容量為j的背包，價值總和最大是多少。
一定要時刻記住這裡i和j的含義，要不然很容易看懵了。
動規五部曲分析如下：
在一維dp數組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。
dp[j]為 容量為j的背包所背的最大價值，那麼如何推導dp[j]呢？
dp[j]可以通過dp[j - weight[j]]推導出來，dp[j - weight[i]]表示容量為j - weight[i]的背包所背的最大價值。
dp[j - weight[i]] + value[i] 表示 容量為 j - 物品i重量 的背包 加上 物品i的價值。（也就是容量為j的背包，放入物品i了之後的價值即：dp[j]）
此時dp[j]有兩個選擇，一個是取自己dp[j]，一個是取dp[j - weight[i]] + value[i]，指定是取最大的，畢竟是求最大價值，
所以遞歸公式為：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);可以看出相對於二維dp數組的寫法，就是把dp[i][j]中i的維度去掉了。
關於初始化，一定要和dp數組的定義吻合，否則到遞推公式的時候就會越來越亂。
dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]，那麼dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。
那麼dp數組除了下標0的位置，初始為0，其他下標應該初始化多少呢？
看一下遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp數組在推導的時候一定是取價值最大的數，如果題目給的價值都是正整數那麼非0下標都初始化為0就可以了，如果題目給的價值有負數，那麼非0下標就要初始化為負無窮。
這樣才能讓dp數組在遞歸公式的過程中取的最大的價值，而不是被初始值覆蓋了。
那麼我假設物品價值都是大於0的，所以dp數組初始化的時候，都初始為0就可以了。
代碼如下：
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}這裡大家發現和二維dp的寫法中，遍歷背包的順序是不一樣的！
二維dp遍歷的時候，背包容量是從小到大，而一維dp遍歷的時候，背包是從大到小。
為什麼呢？
倒敘遍歷是為了保證物品i只被放入一次！，在動態規劃：關於01背包問題，你該了解這些！中講解二維dp數組初始化dp[0][j]時候已經講解到過一次。
舉一個例子：物品0的重量weight[0] = 1，價值value[0] = 15
如果正序遍歷
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此時dp[2]就已經是30了，意味著物品0，被放入了兩次，所以不能正序遍歷。
為什麼倒敘遍歷，就可以保證物品只放入一次呢？
倒敘就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp數組已經都初始化為0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以從後往前循環，每次取得狀態不會和之前取得狀態重合，這樣每種物品就只取一次了。
那麼問題又來了，為什麼二維dp數組歷的時候不用倒敘呢？
因為對於二維dp，dp[i][j]都是通過上一層即dp[i - 1][j]計算而來，本層的dp[i][j]並不會被覆蓋！
（如何這裡讀不懂，大家就要動手試一試了，空想還是不靠譜的，實踐出真知！）
再來看看兩個嵌套for循環的順序，代碼中是先遍歷物品嵌套遍歷背包容量，那可不可以先遍歷背包容量嵌套遍歷物品呢？
不可以！
因為一維dp的寫法，背包容量一定是要倒序遍歷（原因上面已經講了），如果遍歷背包容量放在上一層，那麼每個dp[j]就只會放入一個物品，即：背包裡只放入了一個物品。
（這裡如果讀不懂，就在回想一下dp[j]的定義，或者就把兩個for循環順序顛倒一下試試！）
所以一維dp數組的背包在遍歷順序上和二維其實是有很大差異的！，這一點大家一定要注意。
一維dp，費用用物品0，物品1，物品2 來遍歷背包，最終得到結果如下：
動態規劃-背包問題9一維dp01背包完整C++測試代碼void test_1_wei_bag_problem() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_1_wei_bag_problem();
}可以看出，一維dp 的01背包，要比二維簡潔的多！初始化 和 遍歷順序相對簡單了。
所以我傾向於使用一維dp數組的寫法，比較直觀簡潔，而且空間複雜度還降了一個數量級！
在後面背包問題的講解中，我都直接使用一維dp數組來進行推導。
總結以上的講解可以開發一道面試題目（畢竟力扣上沒原題）。
就是本文中的題目，要求先實現一個純二維的01背包，如果寫出來了，然後再問為什麼兩個for循環的嵌套順序這麼寫？反過來寫行不行？再講一講初始化的邏輯。
然後要求實現一個一維數組的01背包，最後再問，一維數組的01背包，兩個for循環的順序反過來寫行不行？為什麼？
注意以上問題都是在候選人把代碼寫出來的情況下才問的。
就是純01背包的題目，都不用考01背包應用類的題目就可以看出候選人對算法的理解程度了。
相信大家讀完這篇文章，應該對以上問題都有了答案！
此時01背包理論基礎就講完了，我用了兩篇文章把01背包的dp數組定義、遞推公式、初始化、遍歷順序從二維數組到一維數組統統深度剖析了一遍，沒有放過任何難點。
大家可以發現其實信息量還是挺大的。
如果把動態規劃：關於01背包問題，你該了解這些！和本篇的內容都理解了，後面我們在做01背包的題目，就會發現非常簡單了。
不用再憑感覺或者記憶去寫背包，而是有自己的思考，了解其本質，代碼的方方面面都在自己的掌控之中。
即使代碼沒有通過，也會有自己的邏輯去debug，這樣就思維清晰了。
接下來就要開始用這兩天的理論基礎去做力扣上的背包面試題目了，錄友們握緊扶手，我們要上高速啦！
就醬，學算法，認準「代碼隨想錄」，值得你推薦給身邊每一位朋友同學們！