昨天動態(tài)規(guī)劃：關于01背包問題，你該了解這些!中是用二維dp數(shù)組來講解01背包。

今天我們就來說一說滾動數(shù)組，其實在前面的題目中我們已經(jīng)用到過滾動數(shù)組了，就是把二維dp降為一維dp，一些錄友當時還表示比較困惑。

那么我們通過01背包，來徹底講一講滾動數(shù)組!

接下來還是用如下這個例子來進行講解

背包最大重量為4。

物品為：

問背包能背的物品最大價值是多少?

一維dp數(shù)組(滾動數(shù)組)

對于背包問題其實狀態(tài)都是可以壓縮的。

在使用二維數(shù)組的時候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其實可以發(fā)現(xiàn)如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數(shù)組了，只用dp[j](一維數(shù)組，也可以理解是一個滾動數(shù)組)。

這就是滾動數(shù)組的由來，需要滿足的條件是上一層可以重復利用，直接拷貝到當前層。

讀到這里估計大家都忘了 dp[i][j]里的i和j表達的是什么了，i是物品，j是背包容量。

dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。

一定要時刻記住這里i和j的含義，要不然很容易看懵了。

動規(guī)五部曲分析如下：

1.確定dp數(shù)組的定義

在一維dp數(shù)組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。

2.一維dp數(shù)組的遞推公式

dp[j]為 容量為j的背包所背的最大價值，那么如何推導dp[j]呢?

dp[j]可以通過dp[j - weight[i]]推導出來，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數(shù)組中的dp[i-1][j]，即不放物品i，一個是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，畢竟是求最大價值，

所以遞歸公式為：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

可以看出相對于二維dp數(shù)組的寫法，就是把dp[i][j]中i的維度去掉了。

3.一維dp數(shù)組如何初始化

關于初始化，一定要和dp數(shù)組的定義吻合，否則到遞推公式的時候就會越來越亂。

dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]，那么dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。

那么dp數(shù)組除了下標0的位置，初始為0，其他下標應該初始化多少呢?

看一下遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp數(shù)組在推導的時候一定是取價值最大的數(shù)，如果題目給的價值都是正整數(shù)那么非0下標都初始化為0就可以了。

這樣才能讓dp數(shù)組在遞歸公式的過程中取的最大的價值，而不是被初始值覆蓋了。

那么我假設物品價值都是大于0的，所以dp數(shù)組初始化的時候，都初始為0就可以了。

4.一維dp數(shù)組遍歷順序

代碼如下：

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]);

    }
}

這里大家發(fā)現(xiàn)和二維dp的寫法中，遍歷背包的順序是不一樣的!

二維dp遍歷的時候，背包容量是從小到大，而一維dp遍歷的時候，背包是從大到小。

為什么呢?

倒序遍歷是為了保證物品i只被放入一次!。但如果一旦正序遍歷了，那么物品0就會被重復加入多次!

舉一個例子：物品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]就已經(jīng)是30了，意味著物品0，被放入了兩次，所以不能正序遍歷。

為什么倒序遍歷，就可以保證物品只放入一次呢?

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp數(shù)組已經(jīng)都初始化為0)

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以從后往前循環(huán)，每次取得狀態(tài)不會和之前取得狀態(tài)重合，這樣每種物品就只取一次了。

那么問題又來了，為什么二維dp數(shù)組歷的時候不用倒序呢?

因為對于二維dp，dp[i][j]都是通過上一層即dp[i - 1][j]計算而來，本層的dp[i][j]并不會被覆蓋!

(如何這里讀不懂，大家就要動手試一試了，空想還是不靠譜的，實踐出真知!)

再來看看兩個嵌套for循環(huán)的順序，代碼中是先遍歷物品嵌套遍歷背包容量，那可不可以先遍歷背包容量嵌套遍歷物品呢?

不可以!

因為一維dp的寫法，背包容量一定是要倒序遍歷(原因上面已經(jīng)講了)，如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品。

(這里如果讀不懂，就在回想一下dp[j]的定義，或者就把兩個for循環(huán)順序顛倒一下試試!)

所以一維dp數(shù)組的背包在遍歷順序上和二維其實是有很大差異的!，這一點大家一定要注意。

5.舉例推導dp數(shù)組

一維dp，分別用物品0，物品1，物品2 來遍歷背包，最終得到結果如下：

動態(tài)規(guī)劃-背包問題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數(shù)組的寫法，比較直觀簡潔，而且空間復雜度還降了一個數(shù)量級!

在后面背包問題的講解中，我都直接使用一維dp數(shù)組來進行推導。

總結

以上的講解可以開發(fā)一道面試題目(畢竟力扣上沒原題)。

就是本文中的題目，要求先實現(xiàn)一個純二維的01背包，如果寫出來了，然后再問為什么兩個for循環(huán)的嵌套順序這么寫?反過來寫行不行?再講一講初始化的邏輯。

然后要求實現(xiàn)一個一維數(shù)組的01背包，最后再問，一維數(shù)組的01背包，兩個for循環(huán)的順序反過來寫行不行?為什么?

注意以上問題都是在候選人把代碼寫出來的情況下才問的。

就是純01背包的題目，都不用考01背包應用類的題目就可以看出候選人對算法的理解程度了。

相信大家讀完這篇文章，應該對以上問題都有了答案!

此時01背包理論基礎就講完了，我用了兩篇文章把01背包的dp數(shù)組定義、遞推公式、初始化、遍歷順序從二維數(shù)組到一維數(shù)組統(tǒng)統(tǒng)深度剖析了一遍，沒有放過任何難點。

大家可以發(fā)現(xiàn)其實信息量還是挺大的。

如果把動態(tài)規(guī)劃：關于01背包問題，你該了解這些!和本篇的內(nèi)容都理解了，后面我們在做01背包的題目，就會發(fā)現(xiàn)非常簡單了。

不用再憑感覺或者記憶去寫背包，而是有自己的思考，了解其本質，代碼的方方面面都在自己的掌控之中。

即使代碼沒有通過，也會有自己的邏輯去debug，這樣就思維清晰了。

接下來就要開始用這兩天的理論基礎去做力扣上的背包面試題目了，錄友們握緊扶手，我們要上高速啦!

其他語言版本

Java

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定義dp數(shù)組：dp[j]表示背包容量為j時，能獲得的最大價值
        int[] dp = new int[bagWeight + 1];
        //遍歷順序：先遍歷物品，再遍歷背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp數(shù)組
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

Python

def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4
    # 初始化: 全為0
    dp = [0] * (bag_weight + 1)

    # 先遍歷物品, 再遍歷背包容量
    for i in range(len(weight)):
        for j in range(bag_weight, weight[i] - 1, -1):
            # 遞歸公式
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    print(dp)

test_1_wei_bag_problem()

Go

func test_1_wei_bag_problem(weight, value []int, bagWeight int) int {
 // 定義 and 初始化
 dp := make([]int,bagWeight+1)
 // 遞推順序
 for i := 0 ;i < len(weight) ; i++ {
  // 這里必須倒序,區(qū)別二維,因為二維dp保存了i的狀態(tài)
  for j:= bagWeight; j >= weight[i] ; j-- {
   // 遞推公式
   dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  }
 }
 //fmt.Println(dp)
 return dp[bagWeight]
}

func max(a,b int) int {
 if a > b {
  return a
 }
 return b
}


func main() {
 weight := []int{1,3,4}
 value := []int{15,20,30}
 test_1_wei_bag_problem(weight,value,4)
}

javaScript

function testWeightBagProblem(wight, value, size) {
  const len = wight.length,
    dp = Array(size + 1).fill(0);
  for(let i = 1; i <= len; i++) {
    for(let j = size; j >= wight[i - 1]; j--) {
      dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
    }
  }
  return dp[size];
}


function test () {
  console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();