动态规划（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 1new Min 1,1 for 2new Min 1,1,1 for 3new Min 3 for 3new Min 1,3 for 4new Min 4 for 4new Min 1,4 for 5new Min 1,1,4 for 6new 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)))。