摘要：大部分動態規劃能解決的問題，都可以通過回溯演算法來解決，只不過回溯演算法解決起來效率比較低，時間復雜度是指數級的，動態規劃演算法，在執行效率方面，要高很多，
本文分享自華為云社區《深入淺出動態規劃演算法》，作者：嵌入式視覺，
一，動態規劃概念
動態規劃比較適合用來求解最優問題，比如求最大值、最小值等等，它可以非常顯著地降低時間復雜度，提高代碼的執行效率，
它和遞回一樣都非常難學，主要學習難點在于求解問題的程序不太符合人類常規的思維方式，
二，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]; } };
參考資料
初識動態規劃：如何巧妙解決“雙十一”購物時的湊單問題？
點擊關注，第一時間了解華為云新鮮技術~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548732.html
標籤：其他
上一篇：全網最詳細中英文ChatGPT-GPT-4示例檔案-個性化角色智能對話從0到1快速入門——官網推薦的48種最佳應用場景（附python/node.js/curl命令源代碼，小白也能學）
下一篇：git 常用命令