深入淺出動態規劃算法(上)

開啟掘金成長之旅！這是我參與「掘金日新計劃 · 12 月更文挑戰」的第24天，點擊查看活動詳情。

一，動態規劃概念

動態規劃比較適合用來求解最優問題，比如求最大值、最小值等等。它可以非常顯著地降低時間複雜度，提高代碼的執行效率。

它和遞歸一樣都非常難學，主要學習難點在於求解問題的過程不太符合人類常規的思維方式。

二，0-1 揹包問題

對於一組不同重量、不可分割的物品，我們需要選擇一些裝入揹包，在滿足揹包最大重量限制的前提下，揹包中物品總重量的最大值是多少呢？

關於這個 0-1 揹包問題，上一節學習了回溯的解決方法，也就是窮舉搜索所有可能的裝法（時間複雜度指數級），然後找出滿足條件的最大值。有沒有什麼規律，可以有效降低時間複雜度呢？

1，回溯法的求解過程：

直接看代碼，規律是不好的，畫個求解過程圖（遞歸樹）會好看些。假設揹包的最大承載重量是 9，有 5 個不同的物品，每個物品的重量分別是 2，2，4，6，3。求解過程的遞歸樹如下圖所示。

遞歸樹中的每個節點表示一種狀態，我們用（i, cw）來表示。其中，i 表示將要決策第幾個物品是否裝入揹包，cw 表示當前揹包中物品的總重量。比如，（2，2） 表示我們將要決策第 2 個物品是否裝入揹包，在決策前，揹包中物品的總重量是 2。這裏使用回溯算法，從遞歸樹中可以發現其中有些子問題的求解是重複的，且時間複雜度是指數級的。

使用”備忘錄”（記憶化遞歸）的解決方式，記錄已經計算好的 f(i, cw)，當再次計算到重複的 f(i, cw) 的時候，可以直接從備忘錄中取出來用，就不用再遞歸計算了，這樣就可以避免宂餘計算。

```cpp int maxW = 0; int weight[6] = {2,2,4,6,3}; // 物品重量 int n = 5; // 物品個數 int w = 9; // 揹包承受的最大重量 bool mem[5][10]; // 備忘錄，默認值false

// 記憶化遞歸算法實現 class SolutionBacktracking{ public: void f(int i, int cw){ // i 表示放第 i 個物品，cw 表示當前裝進揹包的物品的重量和 if (cw == w || i == n) { // cw==w表示裝滿了，i==n表示物品都考察完了 if(cw > maxW) maxW = cw; return; } if(mem[i][cw]) return; // 重複狀態 mem[i][cw] = true; // 記錄狀態

    f(i+1, cw);  // 不放第 i 個物品
    if(cw+weight[i] <= w)
        f(i+1, cw+weight[i]);  // 放第 i 個物品
}

}; ```

這裏依然是基於回溯算法實現的，但是採用了記憶化遞歸的方法，時間複雜度和空間複雜度都是 $O(n*(w+1))$，$n$ 為物品個數，$w$ 表示揹包承受的最大重量。

2，動態規劃求解過程如下：

把整個求解過程分為 n 個階段，每個階段會決策一個物品是否放到揹包中。每個物品決策（放入或者不放入揹包）完之後，揹包中的物品的重量會有多種情況，也就是説，會達到多種不同的狀態，對應到遞歸樹中，就是有很多不同的節點。

我們把每一層重複的狀態（節點）合併，只記錄不同的狀態，然後基於上一層的狀態集合，來推導下一層的狀態集合。我們可以通過合併每一層重複的狀態，這樣就保證每一層不同狀態的個數都不會超過 w 個（w 表示揹包的承載重量），也就是例子中的 9。於是，我們就成功避免了每層狀態個數的指數級增長。動態規劃方法的計算過程如下圖：

我們用一個二維數組 states[n][w+1]，來記錄每層可以達到的不同狀態。0-1 揹包問題的動態規劃解法的 C++ 代碼如下：

```cpp class SolutionDP1{ public: // weight:物品重量，n:物品個數，w:揹包可承載重量 int knapsack1(int weight[], int n, int w){ vector >states(n, vector(w+1, false)); // 初始化 states 第一個階段的狀態 states[0][0] = true; // 第一個物品不放進揹包 if(weight[0] <= w) states[0][weight[0]] = true; // 第一個物品放進揹包 // 動態規劃-分階段 for(int i=1; i<n;i++){ for(int j=0; j<w; j++) { // 第 i 個物品不放進揹包{} if(states[i-1][j]) states[i][j] = states[i-1][j]; } for(int j=0; j<=w-weight[i];j++){ // 第 i 個物品放入揹包 if(states[i-1][j]) states[i][j+weight[i]] = true; } }

    // 在最後一層變量找到最接近 w 的重量並輸出結果
    for(int i=w; i>0; i--){  
        if(states[n-1][i]) return i;
    }
    return 0;
}

}; ```

這就是一種用動態規劃解決問題的思路。我們把問題分解為多個階段，每個階段對應一個決策。我們記錄每一個階段可達的狀態集合（去掉重複的），然後通過當前階段的狀態集合，來推導下一個階段的狀態集合，動態地往前推進。這也是動態規劃這個名字的由來，你可以自己體會一下

首先，可以分解為多階段，其次，狀態去重，最後當前階段可以利用上一個階段來獲取。這是動態規劃的關鍵。

我們知道回溯算法解決這個問題的時間複雜度是 $O(2^n)$、指數級，那動態規劃解決方案的時間複雜度是多少呢？來分析一下，這個代碼的時間複雜度非常好分析，耗時最多的部分就是代碼中的兩層 for 循環，所以時間複雜度是 $O(n*w)$。$n$ 表示物品個數，$w$ 表示揹包可以承載的總重量。

雖然動態規劃的時間效率較高，但是空間複雜度為 $O(n*w)$，對空間消耗比較大。我們可以考慮用一個大小為 $w+1$ 的一維數組代替二維數組，減少內存消耗。代碼如下：

```cpp class SolutionDP2{ public: // weight:物品重量，n:物品個數，w:揹包可承載重量 int knapsack2(int weight[], int n, int w){ vector states(w+1, false); // int *states=new int [m+1]; // 動態分配,數組長度為 m states[0] = true; // 第一個物品不放進揹包 if(weight[0] < w) states[weight[0]] = true; // 第一個物品放進揹包

    // 動態規劃-分階段
    for(int i=1; i<n;i++){
        for(int j=w-weight[i]; j>=0; j--)  {  // 第 i 個物品放進揹包
            if(states[j]) states[j+weight[i]] = true;
        }
    }

    // 在最後一層變量找到最接近 w 的重量並輸出結果
    for(int i=w;i>0;i--){  
        if(states[i]) return i;
    }
    return 0;
}

}; ```

程序分析：遍歷每個物品，將該物品放入揹包時，在不超過最大重量的前提下，再遍歷查看之前的放入記錄，將之前可能出現的重量的和當前物品的重量相加再記錄下來，等所有方案都嘗試過後，可能出現的揹包重量也都被記錄下來了，最後，從中選擇一個最大值返回。

三，0-1 揹包問題升級版

前面講的揹包問題，只涉及揹包重量和物品重量。現在引入物品價值這一變量。對於一組不同重量、不同價值、不可分割的物品，我們選擇將某些物品裝入揹包，在滿足揹包最大重量限制的前提下，揹包中可裝入物品的總價值最大是多少呢？

1，這個問題依舊可以先用回溯算法來解決，代碼如下：

```cpp // 0-1 揹包問題升級版的回溯解法 int maxV = 0; // 結果放到maxV中 int weight[] = {2，2，4，6，3}; // 物品的重量 int value[] = {3，4，8，9，6}; // 物品的價值 int n = 5; // 物品個數 int w = 9; // 揹包承受的最大重量

class Solution{ public: void f(int i, int cw, int cv) { // 調用f(0, 0, 0) if (cw == w || i == n) { // cw==w表示裝滿了，i==n表示物品都考察完了 if(cv > maxV) maxV = cv; return; } if(cv > maxV) maxV = cv; f(i+1, cw, cv); // 不放第 i 個物品 if(cw+weight[i] <= w) f(i+1, cw+weight[i], cv+value[i]) // 放第 i 個物品 } }; ```

2，使用動態規劃解決這個問題更高效。把整個求解過程分為 $n$ 個階段，每個階段會決策一個物品是否放到揹包中。每個階段決策完之後，揹包中的物品的總重量以及總價值，會有多種情況，也就是會達到多種不同的狀態。我們用一個二維數組 states[n][w+1]，來記錄每層可以達到的不同狀態。

```cpp class SolutionDP3{ int knapsack3(int weight[], int value[], int n, int w) { vector > states(n, vector(w+1, -1)); states[0][0] = 0; // 不放入第 0 個物品 if(weight[0] < w) states[0][weight[0]] = value[0]; // 放入第 0 個物品

    for(int i=1; i<n; i++){
        for(int j=0; j< w; j++){  // 不放入第 i 個物品
            if(states[i-1][j])  states[i][j] = states[i-1][j];
        }

        for(int j=0; j< w-weight[i]; j++){ // 放入第 i 個物品
            int v = states[i-1][j] + values;
            if(v > states[i][j+weight[i]]) 
                states[i][j+weight[i]] = v;
        }
    }

    int maxV = -1;
    for(int j = w; j>=0; j--){
        if(states[n-1][j] > maxV) maxV = states[n-1][j];
    }

    return maxV;
}

} ```

代碼的時間複雜度是 $O(n\cdot w)$，空間複雜度也是 $O(n\cdot w)$。

四，總結

大部分動態規劃能解決的問題，都可以通過回溯算法來解決，只不過回溯算法解決起來效率比較低，時間複雜度是指數級的。動態規劃算法，在執行效率方面，要高很多。儘管執行效率提高了，但是動態規劃的空間複雜度也提高了，所以，很多時候，我們會説，動態規劃是一種空間換時間的算法思想。

五，練習題

5.1，leetcode322 零錢兑換

給你一個整數數組 coins ，表示不同面額的硬幣；以及一個整數 amount ，表示總金額。計算並返回可以湊成總金額所需的 最少的硬幣個數 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數量是無限的。

動態規劃解法的 C++ 代碼如下：

cpp class Solution { public: int coinChange(vector<int>& coins, int amount) { int Max = amount + 1; vector<int> dp(amount + 1, Max); dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int j = 0; j < (int)coins.size(); ++j) { if (coins[j] <= i) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } };

參考資料

初識動態規劃：如何巧妙解決“雙十一”購物時的湊單問題？