数据结构和算法躬行记（8）——动态规划
动态规划（Dynamic Programming，DP）是指在给定的约束条件下求最优值的算法，在解决问题的过程，需要经历多个决策阶段，每个决策阶段都对应着一组状态。
适用于动态规划解决的问题包含三个特征：
（1）最优子结构：通过子问题的最优解，可推导出问题的最优解，即后面阶段的状态可以通过前面阶段的状态推导出来。
（2）无后效性：某阶段状态一旦确定，就不受之后阶段的决策影响。即子问题的解一旦确定，就不再改变。
（3）子问题重叠：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。即有些子问题会被重复计算多次。
动态规划对每个子问题只计算一次，然后将其计算结果保存到一张表中记忆化存储，以便下次需要同一个子问题解时直接查表，从而获得较高的效率，降低了时间复杂度。
一、0-1背包
在之前《回溯》一文中也提到了0-1背包问题，而此处会在背包重量限制的前提下，计算装入物品的最大总价值。
假设背包容量为4斤，吉他（1斤，价值1500）、音响（4斤，价值3000）和笔记本（3斤，价值2000），求背包的最大价值（题目来源于《图解算法 9.1节》）。
先画状态转移表（如下所示），一般是二维的，在画之前需要回答三个问题：
（1）单元格中的值是什么？当前背包中的最大总价值。
（2）如何划分子问题？考虑容量为1、2、3和4的背包，并且将物品依次放入。
（3）网格的坐标轴是什么？横坐标是背包重量，纵坐标是物品。
接下来将计算每个单元格的值。
（1）第一步是将吉他放入背包的四个重量中，而重量1、2和3其实就是在解决各个子问题。
（2）第二步是依次处理音响，判断是否需要放入，经过比对发现只有最大容量才能放入，更新最大价值为3000。
（3）第三步是依次处理笔记本，在背包容量为3斤时更新最大价值为2000，而在4斤时，可同时放入吉他和笔记本，更新最大价值为3500。
根据状态表得出状态转移方程，先计算当前商品价值和剩余空间价值，得到的结果与上一个单元格比对，将较大值填充到当前单元格中。
dp[i][j] = max(goods[i].value + dp[i-1][j-goods[i].weight], dp[i-1][j])
具体的代码实现如下所示，本文的代码仅做参考，没有经过严格的测试用例论证。
function knapsack(goods, w) { let max = Number.MIN_VALUE, dp = [new Array(w)], length = goods.length; for (let j = 1; j <= w; j++) { dp[0][j] = goods[0].value; } for (let i = 1; i < length; i++) { dp[i] = []; for (let j = 1; j <= w; j++) { let rest = j - goods[i].weight; //计算减去当前商品重量后的背包容量 if (rest > 0) { //套用状态转移方程 dp[i][j] = Math.max(goods[i].value + dp[i - 1][rest], dp[i - 1][j]); } else { dp[i][j] = dp[i - 1][j]; //沿用上一个单元格的价值 } if (max < dp[i][j]) max = dp[i][j]; //计算最大值 } } return max; }
二、子串和子序列
1）最长公共子串
最长公共子串是指在不改变字符相对顺序的情况下提取两段字符串中共有的子串，例如fosh和fish，最长公共子串是sh，长度为2（题目来源于《图解算法 9.3节》）。例题：300. 最长上升子序列。
在画状态表之前先回答三个问题：
（1）单元格中的值是什么？公共子串的长度。
（2）如何划分子问题？将两段字符串分割成字符，从前往后依次比对。
（3）网格的坐标轴是什么？横坐标是第一段字符串，纵坐标是第二段字符串。
根据状态表得出状态转移方程，当两个字符相同时，左上角的单元格加一，否则单元格为0。
dp[i][j] = 0 | dp[i-1][j-1] + 1
具体的代码实现如下所示。
function longestCommonSubstr(str1, str2) { let len1 = str1.length, len2 = str2.length, max = Number.MIN_VALUE, dp = []; for (let i = 0; i < len1; i++) { dp[i] = []; for (let j = 0; j < len2; j++) { if (str1[i] != str2[j]) { //两个字符不同 dp[i][j] = 0; continue; } //应对 i-1 或 j-1 小于0的情况 dp[i][j] = i < 1 || j < 1 ? 1 : dp[i - 1][j - 1] + 1; if (max < dp[i][j]) { max = dp[i][j]; } } } return max; }
2）最长公共子序列
还有一个类似的题目是求最长公共子序列，其实就是提取共有的子序列，例如fosh和fish，最长公共子序列是fsh，例题：1143. 最长公共子序列。状态转移表如下所示。
根据状态表得出状态转移方程，当两个字符相同时，仍然是左上角的单元格加一，否则比较左和上两个单元格的值，取较大值。
dp[i][j] = (dp[i-1][j-1] + 1) | max(dp[i-1][j], dp[i][j-1])
具体的代码实现如下所示。
function longestCommonSubsequence(str1, str2) { let len1 = str1.length, len2 = str2.length, max = Number.MIN_VALUE, dp = []; for (let i = 0; i < len1; i++) { dp[i] = []; for (let j = 0; j < len2; j++) { if (str1[i] != str2[j]) { //两个字符不同 dp[i][j] = Math.max( i < 1 ? 0 : dp[i - 1][j], j < 1 ? 0 : dp[i][j - 1] ); max = Math.max(max, dp[i][j]); continue; } //应对 i-1 或 j-1 小于0的情况 dp[i][j] = i < 1 || j < 1 ? 1 : dp[i - 1][j - 1] + 1; max = Math.max(max, dp[i][j]); } } return max; }
3）最长上升子序列
求出一个无序的整数数组中最长上升子序列的长度。例题：300. 最长上升子序列。
网上的解法都是用一维状态转移方程，此处仍然采用二维的解法（可观察各个步骤），其中dp[i][j]是指以第 i 个元素结尾的前 j 个元素中的最长上升子序列。
状态表如下所示，每次只计算dp[i][i]的值，其余值沿用上一行的结果。
根据状态表得出状态转移方程，当第 i 个元素比第 j 个元素大时，在该值的基础上加一，否则默认赋为一。
dp[i][i] = 1 | max(dp[i][j]) + 1
具体的代码实现如下所示。
function lengthOfLIS(nums) { let len = nums.length, max = 1, dp = []; dp[0] = [1]; //初始化dp[0][0]的值 for (let i = 1; i < len; i++) { dp[i] = []; dp[i][i] = 1; //初始化dp[i][i]的值 for (let j = 0; j < i; j++) { //让第i个元素与前j个元素逐一比较 dp[i][j] = dp[i-1][j]; //默认沿用上一行的值 if (nums[i] > nums[j]) { //当第i个元素比第j个元素大时，取其中的较大值 dp[i][i] = Math.max(dp[i][i], dp[i][j] + 1); } } max = Math.max(max, dp[i][i]); } return max; }
三、钱币找零
在《贪心算法》一节中曾提到过钱币找零的问题，此处会加大难度。
假设有几种不同面值的纸币 v1，v2，……，vn（单位是元），如果要支付 w 元，那么最少需要多少张纸币，例如有 3 种不同的纸币，1元、2元、5元，要支付 9元，最少需要 3张纸币。例题：322. 零钱兑换。
在画状态表之前先回答三个问题：
（1）单元格中的值是什么？最少纸币数。
（2）如何划分子问题？考虑要支付1、2…9等金额时，各自需要的最少纸币数。
（3）网格的坐标轴是什么？横坐标是支付金额，纵坐标是可用的纸币。
根据状态表得出状态转移方程，计算金额减去当前面值的剩余金额所用的最少纸币数，将其加一和上一行的最少纸币数做比较，取小值。
dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1)
具体的代码实现如下所示，虽然代码比较长，但好多都是在判断边界条件，以及做各类情况的处理，核心其实还是围绕着状态转移方程。
function coinChange(coins, amount) { let len = coins.length, min = Number.MAX_VALUE, dp = [new Array(amount)]; for (let j = 1; j <= amount; j++) { //初始化第一行 //纸币面值比金额大，或金额无法整除纸币 if(coins[0] > j || (j % coins[0]) > 0) { //对于无法支付金额的情况，赋值为0 dp[0][j] = 0; continue; } dp[0][j] = j / coins[0]; //得到纸币数量 } for (let i = 1; i < len; i++) { dp[i] = []; for (let j = 1; j <= amount; j++) { let rest = j - coins[i]; if(rest == 0) { //可用当前纸币支付金额 dp[i][j] = 1; continue; } if(rest < 0) { //当前纸币比支付金额大 dp[i][j] = dp[i-1][j]; continue; } if(dp[i-1][j] > 0 && dp[i][rest] > 0) { //都可以支付金额 dp[i][j] = Math.min(dp[i-1][j], dp[i][rest] + 1); }else if(dp[i-1][j] > 0) { //只有上一行可以支付金额 dp[i][j] = dp[i-1][j]; }else if(dp[i][rest] > 0) { //只能借助剩余金额的纸币数支付 dp[i][j] = dp[i][rest] + 1; }else { //无法支付 dp[i][j] = 0; } } } //取金额的最小值 for(let i = 0; i < len; i++) { if(dp[i][amount] == 0) { //过滤掉无法支付的数据 continue; } if(dp[i][amount] > 0) { min = Math.min(min, dp[i][amount]); } } return min == Number.MAX_VALUE ? -1 : min; }