貪心算法
回溯算法
分治算法
動態規劃

貪心：一條路走到黑，就一次機會，只能哪邊看著順眼走哪邊
回溯：一條路走到黑，無數次重來的機會，還怕我走不出來 (Snapshot View)
動態規劃：擁有上帝視角，手握無數平行宇宙的歷史存檔， 同時發展出無數個未來 (Versioned Archive View)

初識動態規劃、動態規劃理論、動態規劃實戰

初識動態規劃

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

0-1背包問題

使用回溯算法：

使用回溯法復雜度比較高，是指數級別的，規律不好找。遞歸樹中的每個節點表是一種狀態，我們用（I,cw）來表示。其中，i表示將要決策第幾個物品是否要裝入背包，cw表示當前背包中物品的總重量。如（2,2）表示我們將要決策第2個物品是否要裝入背包，在決策前，背包中的物品總重量是2。

從遞歸樹中，可發現有些子問題的求解是重復的，如圖中f(2,2)和f(3,4)都被重復計算了兩次。我們可借助“備忘錄”的解決方式，記錄已經計算好的f(I,cw)，當再次計算到重復的f(I,cw)的時候，可以直接從備忘錄中取出來用，就不用在遞歸計算了，這樣就可以避免冗余計算。

private int maxW = Integer.MIN_VALUE; // 結果放到maxW中 private int[] weight = {2，2，4，6，3}; // 物品重量 private int n = 5; // 物品個數 private int w = 9; // 背包承受的最大重量 private boolean[][] mem = new boolean[5][10]; // 備忘錄，默認值false public void f(int i, int cw) { // 調用f(0, 0)if (cw == w || i == n) { // cw==w表示裝滿了，i==n表示物品都考察完了if (cw > maxW) maxW = cw;return;}if (mem[i][cw]) return; // 重復狀態mem[i][cw] = true; // 記錄(i, cw)這個狀態f(i+1, cw); // 選擇不裝第i個物品if (cw + weight[i] <= w) {f(i+1,cw + weight[i]); // 選擇裝第i個物品} }

使用動態規劃算法：

把整個求解過程分為n個階段，每個階段會決策一個物品是否放置到背包中。每個物品決策（放入或者不放入背包）完之后，背包中的物品的重量會有很都情況，會達到多種不同的狀態，對應到遞歸樹中，就是很多不同的節點。
把每一層重復的狀態（節點）合并，只記錄不同的狀態，然后基于上一層的狀態集合，來推導下一層的狀態集合。我們可以通過合并每一層重復的狀態，這樣就保證每一層不同狀態的個數都不會超過w個（w表示背包的承載重量），這就避免了每層狀態個數的指數級增長。
用一個二維數組states[n],[w+1]，來記錄每層可以達到的不同狀態

第0個（下標從0開始編號）物品的重量是2，要么轉入背包，要么不裝入背包，決策完之后，會對應背包的兩種狀態，背包中物品的總重量是0或者2。我們用states[0][0]=true和states[0][2]=true來表示這兩種轉態。
第1個物品的重量也是2，基于之前的背包狀態，在這個物品決策完之后，不同的狀態有3個，背包中物品總重量分別是0(0+0)，2(0+2 or 2+0)，4(2+2)。我們用states[1][0]=true，states[1][2]=true，states[1][4]=true來表示這三種狀態。

weight:物品重量，n:物品個數，w:背包可承載重量 public int knapsack(int[] weight, int n, int w) {boolean[][] states = new boolean[n][w+1]; // 默認值falsestates[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] == true) states[i][j] = states[i-1][j];}for (int j = 0; j <= w-weight[i]; ++j) {//把第i個物品放入背包if (states[i-1][j]==true) states[i][j+weight[i]] = true;}}for (int i = w; i >= 0; --i) { // 輸出結果if (states[n-1][i] == true) return i;}return 0; }

用回溯算法解決這個問題的時間復雜度O(2^n)，是指數級的。動態規劃方案的時間復雜度是O(n*w)。n表是物品個數，w表是背包可以承載的總重量。
盡管動態規劃的執行效率比較高，但是我們需要額外申請一個n乘以w+1的二維數組，對空間消耗比較多。所以動態規劃是一種空間換時間的解決思路。
但實際上，只需要一個大小為w+1的一維數組就可以解決這個問題。動態規劃狀態轉移的過程，都可以基于這個一維數組來操作。

public static int knapsack2(int[] items, int n, int w) {boolean[] states = new boolean[w+1]; // 默認值falsestates[0] = true; // 第一行的數據要特殊處理，可以利用哨兵優化if (items[0] <= w) {states[items[0]] = true;}for (int i = 1; i < n; ++i) { // 動態規劃for (int j = w-items[i]; j >= 0; --j) {//把第i個物品放入背包if (states[j]==true) states[j+items[i]] = true;}}for (int i = w; i >= 0; --i) { // 輸出結果if (states[i] == true) return i;}return 0; }

0-1背包問題升級版

基礎的背包問題，只涉及背包的重量和物品重量，現在引入物品價值這個一個變量。對于一組不同重量，不同價值，不可分割的物品，在滿足背包最大重量限制的前提下，背包中可裝入物品的總價值最大是多少？

采用回溯算法：
在遞歸樹中，每個節點表示一個狀態，需要3個變量（I，cw，cv）來表示一個狀態。其中，i表示即將要決策第i個物品是否裝入背包，cw表示當前背包中物品的總重量，cv表示總價值。
在遞歸樹中，有幾個節點的i和cw是完全相同的，比如f(2,2,4)和f(2,2,3)。在背包中物品總重量一樣的情況下，f(2,2,4)這種狀態對應的物品總價值更大，可以舍棄f(2,2,3)這種狀態，只需要沿著f(2,2,4),這條策略線繼續往下決策就可以
即對于（I,cw）相同的不同狀態，我們只需要保留cv值最大的那個，繼續遞歸處理，其他狀態不予考慮。

private int maxV = Integer.MIN_VALUE; // 結果放到maxV中 private int[] items = {2，2，4，6，3}; // 物品的重量 private int[] value = {3，4，8，9，6}; // 物品的價值 private int n = 5; // 物品個數 private int w = 9; // 背包承受的最大重量 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;}f(i+1, cw, cv); // 選擇不裝第i個物品if (cw + weight[i] <= w) {f(i+1,cw+weight[i], cv+value[i]); // 選擇裝第i個物品} }

采用動態規劃算法：
還是把整個求解過程分為n個狀態，每個階段會決策一個物品是否放到背包中。每個決策完之后，背包中的物品的總重量以及總價值，會有多種情況，也就是會達到多種不同的狀態。
用一個二維數組states[n][w+1]，來記錄每層可以達到的不同狀態。不過這里數組存儲的值不在是boolean類型的了，而且當前狀態對應的最大總價值，我們把每一層中（I,cw）重復的狀態（節點）合并，只記錄了cv值最大的那個狀態，然后基于這些狀態來推導下一層的狀態。

public static int knapsack3(int[] weight, int[] value, int n, int w) {int[][] states = new int[n][w+1];for (int i = 0; i < n; ++i) { // 初始化statesfor (int j = 0; j < w+1; ++j) {states[i][j] = -1;}}states[0][0] = 0;if (weight[0] <= w) {states[0][weight[0]] = value[0];}for (int i = 1; i < n; ++i) { //動態規劃，狀態轉移for (int j = 0; j <= w; ++j) { // 不選擇第i個物品if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];}for (int j = 0; j <= w-weight[i]; ++j) { // 選擇第i個物品if (states[i-1][j] >= 0) {int v = states[i-1][j] + value[i];if (v > states[i][j+weight[i]]) {states[i][j+weight[i]] = v;}}}}// 找出最大值int maxvalue = -1;for (int j = 0; j <= w; ++j) {if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];}return maxvalue; }

動態規劃理論

動態規劃理論之最優子結構，無后效性和重復子問題

1，“一個模型三個特征”理論講解
什么樣的問題適合用動態規劃來解決？
（1）“一個模型”
它指的是動態規劃適合解決的問題的模型，“多階段決策最優解模型”。
一般是用動態規劃來解決最優問題，而解決問題的過程，需要經歷多個決策階段。每個決策階段都對應一組狀態。然后我們尋找一組決策序列，經過這組決策序列，能夠產生最終期望求解的最優值。
（2）“三個特征”：
他們分別是最優子結構，無后效性和重復子問題
1，最優子結構：
最優子結構指的是，問題的最優解包含子問題的最優解。即反之講，可以通過子問題的最優解，推導出問題的最優解。
若把最優子結構，對應到前面定義的動態規劃問題模型上，也可以理解為后面階段的狀態可以通過前面階段的狀態推導出來。
2，無后效性：
無后效性有兩層含義，第一層含義是，在推導后面階段的狀態的時候，我們只關心前面階段的狀態值，不關心這個狀態是怎么一步步推導出來的，第二層含義是，某階段狀態一旦確定，就不受之后階段的決策影響，無后效性是一個非常“寬松”的要求。只要滿足前面提到的動態規劃問題模型，基本上都會滿足無后效性。
3，重復子問題
不同的決策序列，到達某個相同的階段時，可能會產生重復的狀態

兩種動態規劃解題思路總結
解決動態規劃問題，一般有兩種思路，分別可叫作，狀態轉移表法和狀態轉移方程法

用回溯算法來解決這個問題。如果你自己寫一下代碼，畫一下遞歸樹，就會發現，遞歸樹中有重復的節點。重復的節點表示，從左上角到節點對應的位置，有多種路線，這也能說明這個問題中存在重復子問題。
如果我們走到 (i, j) 這個位置，我們只能通過 (i-1, j)，(i, j-1) 這兩個位置移動過來，也就是說，我們想要計算 (i, j) 位置對應的狀態，只需要關心 (i-1, j)，(i, j-1) 兩個位置對應的狀態，并不關心棋子是通過什么樣的路線到達這兩個位置的。而且，我們僅僅允許往下和往右移動，不允許后退，所以，前面階段的狀態確定之后，不會被后面階段的決策所改變，所以，這個問題符合“無后效性”這一特征。
剛剛定義狀態的時候，我們把從起始位置 (0, 0) 到 (i, j) 的最小路徑，記作 min_dist(i, j)。因為我們只能往右或往下移動，所以，我們只有可能從 (i, j-1) 或者 (i-1, j) 兩個位置到達 (i, j)。也就是說，到達 (i, j) 的最短路徑要么經過 (i, j-1)，要么經過 (i-1, j)，而且到達 (i, j) 的最短路徑肯定包含到達這兩個位置的最短路徑之一。換句話說就是，min_dist(i, j) 可以通過 min_dist(i, j-1) 和 min_dist(i-1, j) 兩個狀態推導出來。這就說明，這個問題符合“最優子結構”。

1，狀態轉移表法
回溯法-〉遞歸樹-〉重復子問題-〉備忘錄/動態規劃
一般能用動態規劃解決的問題，都可以使用回溯算法的暴力搜索解決。所以，當拿到問題時，可以先用簡單的回溯算法解決，然后定義狀態，每個狀態表示一個節點，然后對應畫出遞歸樹。
從遞歸樹中，很容易可以看出是否存在重復子問題，以及重復子問題是如何產生的。以此來尋找規律，看是否能用動態規劃解決。
找到重復子問題之后，有兩種處理思路，**第一種是直接用回溯加“備忘錄”的方法，來避免重復子問題。**從執行效率上來將，這和動態規劃的解決思路沒有差別，第二種是使用動態規劃的解決方法，狀態轉移表法。
回溯

private int minDist = Integer.MAX_VALUE; // 全局變量或者成員變量 // 調用方式：minDistBacktracing(0, 0, 0, w, n); public void minDistBT(int i, int j, int dist, int[][] w, int n) {// 到達了n-1, n-1這個位置了，這里看著有點奇怪哈，你自己舉個例子看下if (i == n && j == n) {if (dist < minDist) minDist = dist;return;}if (i < n) { // 往下走，更新i=i+1, j=jminDistBT(i + 1, j, dist+w[i][j], w, n);}if (j < n) { // 往右走，更新i=i, j=j+1minDistBT(i, j+1, dist+w[i][j], w, n);} }

遞歸樹

重復子問題

備忘錄/動態規劃

public int minDistDP(int[][] matrix, int n) {int[][] states = new int[n][n];int sum = 0;for (int j = 0; j < n; ++j) { // 初始化states的第一行數據sum += matrix[0][j];states[0][j] = sum;}sum = 0;for (int i = 0; i < n; ++i) { // 初始化states的第一列數據sum += matrix[i][0];states[i][0] = sum;}for (int i = 1; i < n; ++i) {for (int j = 1; j < n; ++j) {states[i][j] = matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);}}return states[n-1][n-1]; }

狀態轉移表法
先畫出一個狀態表，狀態表一般都是二維的其中每個狀態包含三個變量，行，列，數組值。我們根據決策的先后過程，從前往后，根據遞推關系，分階段填充狀態表中的每個狀態。最后，將這個遞推填表的過程，翻譯成代碼，就是動態規劃代碼了。

狀態轉移方程法：
狀態轉移方程有點類似遞歸的解題思路，需要分析，某個問題如何通過子問題來遞歸求解，也就是所謂的最優子結構。根據最優子結構，寫出遞歸公式，也就是所謂的狀態轉移方程。有了狀態轉移方程，代碼實現就非常簡單了，一般情況下，有兩種代碼實現的方法，一種是遞歸加“備忘錄”，另一種是迭代遞推。

private int[][] matrix = {{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}}; private int n = 4; private int[][] mem = new int[4][4]; public int minDist(int i, int j) { // 調用minDist(n-1, n-1);if (i == 0 && j == 0) return matrix[0][0];if (mem[i][j] > 0) return mem[i][j];int minLeft = Integer.MAX_VALUE;if (j-1 >= 0) {minLeft = minDist(i, j-1);}int minUp = Integer.MAX_VALUE;if (i-1 >= 0) {minUp = minDist(i-1, j);}int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);mem[i][j] = currMinDist;return currMinDist; }

狀態轉移方程是解決動態規劃的關鍵，如果能寫出狀態轉移方程，那動態規劃問題基本上就解決一大半了，但是很多動態規劃問題的狀態本身就不好定義，狀態轉移方程也就更不好想到。

狀態轉移表法解題思路大致可以概括為，回溯算法實現 - 定義狀態 - 畫遞歸樹 - 找重復子問題 - 畫狀態轉移表 - 根據遞推關系填表 - 將填表過程翻譯成代碼。
狀態轉移方程法的大致思路可以概括為，找最優子結構 - 寫狀態轉移方程 - 將狀態轉移方程翻譯成代碼。

動態規劃實戰

實現搜索引擎中的拼寫糾錯功能

編輯距離

萊文斯坦距離（Levenshtein distance）和最長公共子串長度（Longest common substring length）。其中，萊文斯坦距離允許增加、刪除、替換字符這三個編輯操作，最長公共子串長度只允許增加、刪除字符這兩個編輯操作。

萊文斯坦距離（Levenshtein distance）

最長公共子串長度


當用戶在搜索框內，輸入一個拼寫錯誤的單詞時，我們就拿這個單詞跟詞庫中的單詞一一進行比較，計算編輯距離，將編輯距離最小的單詞，作為糾正之后的單詞，提示給用戶。

[筆記整理來源： 王爭 數據結構與算法之美](htt ps://s1.ax1x.com/2020/08/03/aUh2TS.png)

總結

以上是生活随笔為你收集整理的【数据结构与算法】【算法思想】动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。