聊聊不太符合常規思維的動態規劃演算法

摘要：大部分動態規劃能解決的問題，都可以通過回溯演算法來解決，只不過回溯演算法解決起來效率比較低，時間復雜度是指數級的，動態規劃演算法，在執行效率方面，要高很多，

本文分享自華為云社區《深入淺出動態規劃演算法》，作者：嵌入式視覺，

一，動態規劃概念

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

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

二，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) 的時候，可以直接從備忘錄中取出來用，就不用再遞回計算了，這樣就可以避免冗余計算，

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))O(n?(w+1))，nn 為物品個數，ww 表示背包承受的最大重量，

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

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

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

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

class SolutionDP1{
public:
 // weight:物品重量，n:物品個數，w:背包可承載重量
    int knapsack1(int weight[], int n, int w){
        vector<vector<bool> >states(n, vector<bool>(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(2n)O(2n)、指數級，那動態規劃解決方案的時間復雜度是多少呢？來分析一下，這個代碼的時間復雜度非常好分析，耗時最多的部分就是代碼中的兩層 for 回圈，所以時間復雜度是 O(n?w)O(n?w)，nn 表示物品個數，ww 表示背包可以承載的總重量，

雖然動態規劃的時間效率較高，但是空間復雜度為 O(n?w)O(n?w)，對空間消耗比較大，我們可以考慮用一個大小為 w+1w+1 的一維陣列代替二維陣列，減少記憶體消耗，代碼如下：

class SolutionDP2{
public:
 // weight:物品重量，n:物品個數，w:背包可承載重量
    int knapsack2(int weight[], int n, int w){
        vector<bool> 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，這個問題依舊可以先用回溯演算法來解決，代碼如下：

// 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，使用動態規劃解決這個問題更高效，把整個求解程序分為 nn 個階段，每個階段會決策一個物品是否放到背包中，每個階段決策完之后，背包中的物品的總重量以及總價值，會有多種情況，也就是會達到多種不同的狀態，我們用一個二維陣列 states[n][w+1]，來記錄每層可以達到的不同狀態，

class SolutionDP3{
    int knapsack3(int weight[], int value[], int n, int w) {
        vector<vector<int> > states(n, vector<int>(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?w)O(n?w)，空間復雜度也是 O(n?w)O(n?w)，

四，總結

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

五，練習題

5.1，leetcode322 零錢兌換

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

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

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

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

參考資料

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

點擊關注，第一時間了解華為云新鮮技術~

標籤：其他

上一篇：全網最詳細中英文ChatGPT-GPT-4示例檔案-個性化角色智能對話從0到1快速入門——官網推薦的48種最佳應用場景（附python/node.js/curl命令源代碼，小白也能學）

下一篇：一個有效的圖表影像資料提取框架