讀古今文學網 > 學習JavaScript數據結構與算法（第2版） > 11.2 動態規劃 >

11.2 動態規劃

動態規劃（Dynamic Programming，DP）是一種將複雜問題分解成更小的子問題來解決的優化技術。

本書之前提到過幾次動態規劃技術。用動態規劃解決的一個問題是第9章中的深度優先搜索。

　要注意動態規劃和分而治之（歸並排序和快速排序算法中用到的那種）是不同的方法。分而治之方法是把問題分解成相互獨立的子問題，然後組合它們的答案，而動態規劃則是將問題分解成相互依賴的子問題。

另一個例子是上一節解決的斐波那契問題。我們將斐波那契問題分解成如該節圖示的小問題。

用動態規劃解決問題時，要遵循三個重要步驟：

(1) 定義子問題；

(2) 實現要反覆執行來解決子問題的部分（這一步要參考前一節討論的遞歸的步驟）；

(3) 識別並求解出邊界條件。

能用動態規劃解決的一些著名的問題如下。

  • 背包問題：給出一組項目，各自有值和容量，目標是找出總值最大的項目的集合。這個問題的限制是，總容量必須小於等於「背包」的容量。

  • 最長公共子序列：找出一組序列的最長公共子序列（可由另一序列刪除元素但不改變餘下元素的順序而得到）。

  • 矩陣鏈相乘：給出一系列矩陣，目標是找到這些矩陣相乘的最高效辦法（計算次數盡可能少）。相乘操作不會進行，解決方案是找到這些矩陣各自相乘的順序。

  • 硬幣找零：給出面額為d1…dn的一定數量的硬幣和要找零的錢數，找出有多少種找零的方法。

  • 圖的全源最短路徑：對所有頂點對(u, v)，找出從頂點u到頂點v的最短路徑。我們在第9章已經學習過這個問題的Floyd-Warshall算法。

接下來幾節，我們會一一講解這些問題。

　在Google、Amazon、Microsoft、Oracle等大公司的編程面試中，這些問題及其解決方案非常常見。

11.2.1　最少硬幣找零問題

最少硬幣找零問題是硬幣找零問題的一個變種。硬幣找零問題是給出要找零的錢數，以及可用的硬幣面額d1…dn及其數量，找出有多少種找零方法。最少硬幣找零問題是給出要找零的錢數，以及可用的硬幣面額d1…dn及其數量，找到所需的最少的硬幣個數。

例如，美國有以下面額（硬幣）：d1=1，d2=5，d3=10，d4=25。

如果要找36美分的零錢，我們可以用1個25美分、1個10美分和1個便士（1美分）。

如何將這個解答轉化成算法？

最少硬幣找零的解決方案是找到n所需的最小硬幣數。但要做到這一點，首先得找到對每個x<n的解。然後，我們將解建立在更小的值的解的基礎上。

來看看算法： 

function MinCoinChange(coins){
  var coins = coins; //{1}
  var cache = {};    //{2}

  this.makeChange = function(amount) {
    var me = this;
    if (!amount) { //{3}
      return ;
    }
    if (cache[amount]) { //{4}
      return cache[amount];
    }
    var min = , newMin, newAmount;
    for (var i=0; i<coins.length; i++){ //{5}
      var coin = coins[i];
      newAmount = amount - coin; //{6}
      if (newAmount >= 0){
        newMin = me.makeChange(newAmount); //{7}
      }
      if (
        newAmount >= 0 && //{8}
        (newMin.length < min.length-1 || !min.length)//{9}
        && (newMin.length || !newAmount) //{10})
        {
          min = [coin].concat(newMin); //{11}
          console.log(\'new Min \' + min + \' for \' + amount);
      }
    }
    return (cache[amount] = min); //{12}
  };
}

為了更有條理，我們創建了一個類，解決給定面額的最少硬幣找零問題。讓我們一步步解讀這個算法。

MinCoinChange類接收coins參數（行{1}），該參數代表問題中的面額。對美國的硬幣系統而言，它是[1, 5, 10, 25]。我們可以隨心所欲傳遞任何面額。此外，為了更加高效且不重複計算值，我們使用了cache（行{2}）。

接下來是makeChange方法，它也是一個遞歸函數，找零問題由它解決。首先，若amount不為正（< 0），就返回空數組（行{3}）；方法執行結束後，會返回一個數組，包含用來找零的各個面額的硬幣數量（最少硬幣數）。接著，檢查 cache緩存。若結果已緩存（行{4}），則直接返回結果；否則，執行算法。

我們基於coins參數（面額）解決問題。因此，對每個面額（行{5}），我們都計算newAmount（行{6}）的值，它的值會一直減小，直到能找零的最小錢數（別忘了本算法對所有的x < amount都會計算makeChange結果）。若newAmount是合理的值（正值），我們也會計算它的找零結果（行{7}）。

最後，我們判斷newAmount是否有效，minValue （最少硬幣數）是否是最優解，與此同時minValue和newAmount是否是合理的值（{行10}）。若以上判斷都成立，意味著有一個比之前更優的答案（行{11}。以5美分為例，可以給5便士或者1個5美分鎳幣，1個5美分鎳幣是最優解）。最後，返回最終結果（行{12}）。

測試一下這個算法： 

var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
console.log(minCoinChange.makeChange(36));

要知道，如果我們檢查cache變量，會發現它存儲了從1到36美分的所有結果。以上代碼的結果是[1, 10, 25]。

本書的源碼中會有幾行多餘的代碼，輸出算法的步驟。例如，使用面額[1, 3, 4]，並對錢數6執行算法，會產生以下輸出： 

new Min 1 for 1
new Min 1,1 for 2
new Min 1,1,1 for 3
new Min 3 for 3
new Min 1,3 for 4
new Min 4 for 4
new Min 1,4 for 5
new Min 1,1,4 for 6
new Min 3,3 for 6
[3, 3]

所以，找零錢數為6時，最佳答案是兩枚價值為3的硬幣。

11.2.2　背包問題

背包問題是一個組合優化問題。它可以描述如下：給定一個固定大小、能夠攜重W的背包，以及一組有價值和重量的物品，找出一個最佳解決方案，使得裝入背包的物品總重量不超過W，且總價值最大。

下面是一個例子：

物品#

重量

價值

1

2

3

2

3

4

3

4

5

考慮背包能夠攜帶的重量只有5。對於這個例子，我們可以說最佳解決方案是往背包裡裝入物品1和物品2，這樣，總重量為5，總價值為7。

　這個問題有兩個版本。0-1版本只能往背包裡裝完整的物品，而分數背包問題則允許裝入分數物品。在這個例子裡，我們將處理該問題的0-1版本。動態規劃對分數版本無能為力，但本章稍後要學習的貪心算法可以解決它。

我們來看看下面這個背包算法： 

function knapSack(capacity, weights, values, n) {

  var i, w, a, b, kS = ;

  for (i = 0; i <= n; i++) { //{1}
    kS[i] = ;
  }

  for (i = 0; i <= n; i++) {
    for (w = 0; w <= capacity; w++) {
      if (i == 0 || w == 0) { //{2}
        kS[i][w] = 0;
      } else if (weights[i-1] <= w) { //{3}
        a = values[i-1] + kS[i-1][w-weights[i-1]];
        b = kS[i-1][w];
        kS[i][w] = (a > b) ? a : b; //{4} max(a,b)
      } else {
        kS[i][w] = kS[i-1][w]; //{5}
      }
    }
  }
  return kS[n][capacity]; //{6}
}

我們來看看這個算法是如何工作的。

  • 行{1}：首先，初始化將用於尋找解決方案的矩陣ks[n+1][capacity+1]。

  • 行{2}：忽略矩陣的第一列和第一行，只處理索引不為0的列和行。

  • 行{3}：物品i的重量必須小於約束（capacity）才有可能成為解決方案的一部分；否則，總重量就會超出背包能夠攜帶的重量，這是不可能發生的。發生這種情況時，只要忽略它，用之前的值就可以了（行{5}）。

  • 行{4}：當找到可以構成解決方案的物品時，選擇價值最大的那個。

  • 行{6}：最後，問題的解決方案就在這個二維表格右下角的最後一個格子裡。

我們可以用開頭的例子來測試這個算法： 

var values = [3, 4, 5],
  weights = [2, 3, 4],
  capacity = 5,
  n = values.length;
console.log(knapSack(capacity, weights, values, n)); //輸出 7

下圖舉例說明了例子中kS矩陣的構造：

請注意，這個算法只輸出背包攜帶物品價值的最大值，而不列出實際的物品。我們可以增加下面的附加函數來找出構成解決方案的物品： 

function findValues(n, capacity, kS, weights, values) {
  var i = n, k = capacity;
  console.log(\'解決方案包含以下物品：\');

  while (i > 0 && k > 0) {
    if (kS[i][k] !== kS[i-1][k]) {
      console.log(\'物品\' + i + \'，重量：\' + weights[i-1] + \'，價值：\' + values[i-1]);
      i--;
      k = k - kS[i][k];
    } else {
      i--;
    }
  }
}

我們可以在knapsack函數的行{6}之前調用這個函數。執行完整的算法，會得到如下輸出： 

解決方案包含以下物品：
物品2，重量：4，價值：3
物品1，重量：3，價值：2
總價值：7

　背包問題也可以寫成遞歸形式。你可以在本書的源碼包中找到它的遞歸版本。

11.2.3　最長公共子序列

另一個經常被當作編程挑戰問題的動態規劃問題是最長公共子序列（LCS）：找出兩個字符串序列的最長子序列的長度。最長子序列是指，在兩個字符串序列中以相同順序出現，但不要求連續（非字符串子串）的字符串序列。

考慮如下例子：

再看看下面這個算法： 

function lcs(wordX, wordY) {
  var m = wordX.length,
  n = wordY.length,
  l = ,
  i, j, a, b;

  for (i = 0; i <= m; ++i) {
    l[i] = ;
    //{1}
    for (j = 0; j <= n; ++j) {
      l[i][j] = 0;
      //{2}
    }
  }

  for (i = 0; i <= m; i++) {
    for (j = 0; j <= n; j++) {
      if (i == 0 || j == 0) {
        l[i][j] = 0;
      } else if (wordX[i-1] == wordY[j-1]) {
        l[i][j] = l[i-1][j-1] + 1;
        //{3}
        } else {
          a = l[i-1][j];
          b = l[i][j-1];
          l[i][j] = (a > b) ? a : b; //max(a, b)
          //{4}
        }
      }
    }
    //{5}
    return l[m][n];
}

比較背包問題和LCS算法，我們會發現兩者非常相似。這項從頂部開始構建解決方案的技術被稱為記憶，而解決方案就在表格或矩陣的右下角。

像背包問題算法一樣，這種方法只輸出LCS的長度，而不包含LCS的實際結果。要提取這個信息，需要對算法稍作修改，聲明一個新的solution矩陣。注意，代碼中有一些註釋，我們需要用以下代碼替換這些註釋。

  • 行{1}：solution[i] = ;

  • 行{2}：solution[i][j] = \'0\';

  • 行{3}：solution[i][j] = \'diagonal\';

  • 行{4}：solution[i][j]=(l[i][j] == l[i-1][j]) ? \'top\' : \'left\';

  • 行{5}：printSolution(solution, l, wordX, wordY, m, n);

printSolution函數如下： 

function printSolution(solution, l, wordX, wordY, m, n) {
  var a = m, b = n, i, j,
  x = solution[a][b],
  answer = \'\';

  while (x !== \'0\') {
    if (solution[a][b] === \'diagonal\') {
      answer = wordX[a - 1] + answer;
      a--;
      b--;
    } else if (solution[a][b] === \'left\') {
      b--;
    } else if (solution[a][b] === \'top\') {
      a--;
    }
    x = solution[a][b];
  }
  console.log(\'lcs: \'+ answer);
}

當解矩陣的方向為對角線時，我們可以將字符添加到答案中。

如果用\'acbaed\'和\'abcadf\'兩個字符串執行上面的算法，我們將得到輸出4。用於構建結果的矩陣l看起來像下面這樣。我們也可以用附加的算法來跟蹤LCS的值（如下圖高亮所示）。

通過上面的矩陣，我們知道LCS算法的結果是長度為4的acad。

　LCS問題也可以寫成遞歸形式。你可以在本書的源碼包中找到它的遞歸版本。

11.2.4　矩陣鏈相乘

矩陣鏈相乘是另一個可以用動態規劃解決的著名問題。這個問題是要找出一組矩陣相乘的最佳方式（順序）。

讓我們試著更好地理解這個問題。n 行m 列的矩陣A和m 行p 列的矩陣B相乘，結果是n 行p 列的矩陣C。

考慮我們想做A*B*C*D的乘法。因為乘法滿足結合律，所以我們可以讓這些矩陣以任意順序相乘。因此，考慮如下情況：

  • A是一個10行100列的矩陣

  • B是一個100行5列的矩陣

  • C是一個5行50列的矩陣

  • D是一個50行1列的矩陣

  • A*B*C*D的結果是一個10行1列的矩陣

在這個例子裡，相乘的方式有五種。

(1) (A(B(CD)))：乘法運算的次數是1750次。

(2) ((AB)(CD))：乘法運算的次數是5300次。

(3) (((AB)C)D)：乘法運算的次數是8000次。

(4) ((A(BC))D)：乘法運算的次數是75 500次。

(5) (A((BC)D))：乘法運算的次數是31 000次。

相乘的順序不一樣，要進行的乘法運算總數也有很大差異。那麼，要如何構建一個算法，求出最少的乘法運算操作次數？矩陣鏈相乘的算法如下： 

function matrixChainOrder(p, n) {
  var i, j, k, l, q, m = ;

  for (i = 1; i <= n; i++) {
    m[i] = ;
    m[i][i] = 0;
  }

  for (l = 2; l < n; l++) {
    for (i = 1; i <= n-l+1; i++) {
      j = i+l-1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (k = i; k <= j-1; k++) {
        q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; //{1}
        if (q < m[i][j]){
          m[i][j] = q;
          //{2}
        }
      }
    }
  }
  //{3}
  return m[1][n-1];
}

整個算法中最重要的是行{1}，神奇之處全都在這一行。它計算了給定括號順序的乘法運算次數，並將值保存在輔助矩陣m中。

對開頭的例子執行上面的算法，會得到結果7500；正如我們前面提到的，這是最少的操作次數。看看這個： 

var p = [10, 100, 5, 50, 1],
n = p.length;
console.log(matrixChainOrder(p, n));

然而，這個算法也不會給出最優解的括號順序。為了得到這些信息，我們可以對代碼做一些改動。

首先，我們需要通過以下代碼聲明並初始化一個輔助矩陣s： 

var s = ;
for (i = 0; i <= n; i++) {
  s[i] = ;
  for (j = 0; j <= n; j++) {
    s[i][j] = 0;
  }
}

然後，在matrixChainOrder函數的行{2}添加下面的代碼： 

s[i][j] = k;

在行{3}，我們調用打印括號的函數，如下： 

printOptimalParenthesis(s, 1, n-1);

最後，我們的printOptimalParenthesis函數如下： 

function printOptimalParenthesis(s, i, j) {
  if (i == j) {
    console.log(\"A[\" + i + \"]\");
  } else {
    console.log(\"(\");
    printOptimalParenthesis(s, i, s[i][j]);
    printOptimalParenthesis(s, s[i][j] + 1, j);
    console.log(\")\");
  }
}

執行修改後的算法，也能得到括號的最佳順序(A[1](A[2](A[3]A[4])))，並可以轉化為(A(B(CD)))。

    學習JavaScript數據結構與算法（第2版）