今天我們來學(xué)習(xí)一個非常出名的算法思想：動態(tài)規(guī)劃。說它出名，不僅因?yàn)樗容^高效地解決了某一類問題，還因?yàn)樗隽嗣仉y學(xué)...沒錯，你要集中注意，我們要發(fā)車了

動態(tài)規(guī)劃的適用范圍

算法有它特定的可以解決的一類問題，對于動態(tài)規(guī)劃來說，它能解決一個模型，三個特征的問題。

一個模型

一個模型是指：多階段決策最優(yōu)解模型

我們一般是使用動態(tài)規(guī)劃來解決最優(yōu)問題。解決這類問題的過程，需要經(jīng)歷多個決策階段。每個決策的階段都會對應(yīng)一組狀態(tài)。在所有的決策中，我們尋找一組決策，這一組決策可以產(chǎn)生最終期望求解的最優(yōu)值。

三個特征

它們分別是：最優(yōu)子結(jié)構(gòu)、無后效性、重復(fù)子問題。

1.最優(yōu)子結(jié)構(gòu)

最優(yōu)子結(jié)構(gòu)：一個問題的最優(yōu)解包含了子問題的最優(yōu)解。反過來思考，我們可以通過多個子問題的最優(yōu)解來推出問題的最優(yōu)解。

利用最優(yōu)子結(jié)構(gòu)的的特點(diǎn)，我們可以從結(jié)果逐漸向前遞歸得到問題的解（自后向前）。實(shí)際上，這也是使用狀態(tài)轉(zhuǎn)移方程法求解動態(tài)規(guī)劃問的思想來源。

2.無后效性

無后效性包含兩層含義：

• 在向后推導(dǎo)的時候，我們只關(guān)心當(dāng)前階段的狀態(tài)值，而不必追問這個狀態(tài)是如何推導(dǎo)的。
• 一旦某個狀態(tài)被確定，它就不會收到之后的決策影響。

無后效性是非常寬松的條件，只要滿足多階段最優(yōu)解模型，基本上都會滿足無后效性。

3.重復(fù)子問題

在不同的決策序列中，達(dá)到某個相同的階段時，可能會產(chǎn)生重復(fù)的狀態(tài)。

這個問題會帶來兩點(diǎn)影響：

• 在使用回溯法解決這類問題的時候，會存在大量的重復(fù)計算。我們可以通過設(shè)置備忘錄來避免重復(fù)計算。
• 在動態(tài)規(guī)劃的解決方案中，有一種狀態(tài)轉(zhuǎn)移表法，它的思想是從前先后保存所有解的狀態(tài)，從中尋找最優(yōu)解。這種方法就會通過“剪枝”的方式減小計算。（和回溯設(shè)置備忘錄是一樣的解決思路）

案例剖析

下面就通過一個例子講解“一個模型，三個特征”的應(yīng)用。
問題描述：

假設(shè)我們有一個 n 乘以 n 的矩陣 w[n][n]。矩陣存儲的都是正整數(shù)。棋子起始位置在左上角，終止位置在右下角。我們將棋子從左上角移動到右下角。每次只能向右或者向下移動一位。從左上角到右下角，會有很多不同的路徑可以走。我們把每條路徑經(jīng)過的數(shù)字加起來看作路徑的長度。那從左上角移動到右下角的最短路徑長度是多少呢？

適用條件-案例.jpg

一個模型：多階段最優(yōu)解

• 從 (0,0) 走到 (n-1,n-1) ，總共要走 2(n-1) 步，也就對應(yīng) 2(n-1) 個階段。符合多階段條件。
• 從 (0,0) 走到 (n-1,n-1) ，有非常多條路徑可以選擇，而其中有一條可以做到路徑最短。符合具備最優(yōu)解的條件

三個特征

• 從某點(diǎn)到另一個點(diǎn)，會有多個不同的路線，也就是說，這個問題中存在重復(fù)子問題：

  案例-重復(fù)子問題.jpg

• 走到某一點(diǎn)，我們只能通過該點(diǎn)的左邊和上邊到達(dá)，所以對于某一點(diǎn)的狀態(tài)，我們只需要關(guān)注這個點(diǎn)左方和上方的狀態(tài)，而不必關(guān)心如何到達(dá)這個位置；經(jīng)由某一點(diǎn)，只能到達(dá)它下方和右方的點(diǎn)，所以前面階段的狀態(tài)確定之后，不會因?yàn)楹竺骐A段的決策改變。
  綜上，這個問題符合無后效性。

• 走到終點(diǎn)，可以由這個點(diǎn)的左方和上方的狀態(tài)得出（取兩者中最優(yōu)的路線）。這符合最優(yōu)子結(jié)構(gòu)。

兩種解題思路

解決動態(tài)規(guī)劃問題，一般有兩種解題思路：狀態(tài)轉(zhuǎn)移表法 和 狀態(tài)轉(zhuǎn)移方程法。前者利用了問題的重復(fù)子問題特性，后者利用了最優(yōu)子結(jié)構(gòu)特性

1.狀態(tài)轉(zhuǎn)移表法

所有的動態(tài)規(guī)劃問題都可以使用回溯法解決，即使回溯會帶來大量重復(fù)計算，但是我們可以通過模擬回溯法的求解過程構(gòu)建一個問題的解空間。（這個解空間是一個遞歸樹，包含了所有可能的解）這里，你回溯算法的代碼：

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

你可以思考計算機(jī)探索解空間的過程，最終它會形成一個遞歸樹：

案例-遞歸樹.jpg

在遞歸樹中，一個狀態(tài)（也就是一個節(jié)點(diǎn)）包含三個變量 (i, j, dist)，其中 i，j 分別表示行和列，dist 表示從起點(diǎn)到達(dá) (i, j) 的路徑長度。從圖中，我們看出，盡管 (i, j, dist) 不存在重復(fù)的，但是 (i, j) 重復(fù)的有很多。對于 (i, j) 重復(fù)的節(jié)點(diǎn)，我們只需要選擇 dist 最小的節(jié)點(diǎn)，繼續(xù)遞歸求解，其他節(jié)點(diǎn)就可以舍棄了。

既然問題中存在重復(fù)子問題，我們就可以嘗試使用動態(tài)規(guī)劃解決：

我們畫出一個二維狀態(tài)表，表中的行、列表示棋子所在的位置，表中的數(shù)值表示從起點(diǎn)到這個位置的最短路徑。我們按照決策過程，通過不斷狀態(tài)遞推演進(jìn)，將狀態(tài)表填好。為了方便代碼實(shí)現(xiàn)，我們按行來進(jìn)行依次填充。

案例-重復(fù)子問題-狀態(tài)轉(zhuǎn)移1.jpg

案例-重復(fù)子問題-狀態(tài)轉(zhuǎn)移2.jpg

理解了這個過程，我們可以很容易的寫出相關(guā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的第一行數(shù)據(jù)
    sum += matrix[0][j];
    states[0][j] = sum;
  }
  sum = 0;
  for (int i = 0; i < n; ++i) { // 初始化states的第一列數(shù)據(jù)
    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];
}

使用了備忘錄的回溯算法和上面的動態(tài)規(guī)劃過程的性能差不多，但是有些問題我們無法設(shè)置備忘錄，所以你需要了解狀態(tài)轉(zhuǎn)移表這種規(guī)劃方法。

2.狀態(tài)轉(zhuǎn)移方程法

狀態(tài)轉(zhuǎn)移方程，有點(diǎn)類似遞歸的解題思路。我們要分析一個問題是如何通過子問題來遞歸求解的，也就是使用最優(yōu)子結(jié)構(gòu)寫出狀態(tài)轉(zhuǎn)移方程。一旦寫出狀態(tài)轉(zhuǎn)移方程，代碼的實(shí)現(xiàn)就非常簡單了。

依然以剛才的例子舉例，我們已經(jīng)分析過了它的最優(yōu)子結(jié)構(gòu)，根據(jù)這個結(jié)構(gòu)，我們可以寫出它的狀態(tài)轉(zhuǎn)移方程：

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

利用轉(zhuǎn)移方程，我們可以很方便地構(gòu)造遞歸代碼：

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) { // 調(diào)用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;
}

3.小結(jié)

你會發(fā)現(xiàn)，狀態(tài)轉(zhuǎn)移表法是從起始點(diǎn)逐步向終止點(diǎn)前進(jìn)，整個過程中我們需要保存某路徑下的狀態(tài)，由于我們求解最優(yōu)化問題，且問題中會存在重復(fù)子問題，所以我們可以通過選取最優(yōu)狀態(tài)減少計算量。

而狀態(tài)轉(zhuǎn)移方程法是一個從結(jié)果向起始追溯的過程，這就要求我們可以通過結(jié)果向前追溯，而追溯的線索就是此類問題的有最優(yōu)子結(jié)構(gòu)。

兩種操作方法沒有優(yōu)劣之分，實(shí)際上，兩種方法或多或少都會使用到動態(tài)規(guī)劃問題的三個特點(diǎn)。至于具體如何選擇，就需要分析具體問題了。

四種算法思想的比較（?。。。?/h1>

我們一共學(xué)習(xí)了 分治、貪心、回溯、動態(tài)規(guī)劃 四種算法思想。

• 分治算法比較獨(dú)特，它希望一個問題可以分解成若干個規(guī)模小的問題，且各個子問題之間沒有相關(guān)性（或盡可能小），所以這一類的問題無法分解成多階段決策模型，這也是它最與眾不同之處。

• 貪心、回溯、動態(tài)規(guī)劃都可以抽象成為多階段最優(yōu)解決策模型，但是他們都有各自的特點(diǎn)。

• 貪心：貪心算法可以看做動態(tài)規(guī)劃的一個特殊情況，這個特殊之處在于，貪心算法相信局部最優(yōu)解可以產(chǎn)生全局最優(yōu)解。

• 回溯：回溯算法是個“萬金油”?？梢允褂脛討B(tài)規(guī)劃、貪心解決的問題都可以使用回溯算法解決。回溯算法相當(dāng)于窮舉搜索，它通過遍歷問題的解空間，對比所有可能的解，找到最優(yōu)的解。但是回溯算法的時間復(fù)雜度非常高，在某些情況下我們可以使用 “備忘錄” 減少計算。如果無法使用備忘錄，那我們可以考慮使用動態(tài)規(guī)劃。

• 動態(tài)規(guī)劃：動態(tài)規(guī)劃需要滿足一個模型、三個特征，它高效的原因之一就是對重復(fù)子問題的剪枝。解決動態(tài)規(guī)劃的思路大致可以分為兩種：

1. 回溯實(shí)現(xiàn) - 定義狀態(tài) - 畫遞歸樹 - 找重復(fù)子問題 - 畫狀態(tài)轉(zhuǎn)移表 - 根據(jù)遞推關(guān)系填表 - 將填表過程翻譯成代碼。
2. 找最優(yōu)子結(jié)構(gòu) - 寫狀態(tài)轉(zhuǎn)移方程 - 將狀態(tài)轉(zhuǎn)移方程翻譯成代碼。

---

以上就是動態(tài)規(guī)劃的全部內(nèi)容

注：本文章的主要內(nèi)容來自我對極客時間app的《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄的總結(jié)，我使用了大量的原文、代碼和截圖，如果想要了解具體內(nèi)容，可以前往極客時間