如果不能避免被剥削的命运，就要提高自己被剥削的价值。
大家好，我是柒八九。
今天，我们继续探索JS算法相关的知识点。我们来谈谈关于动态规划的相关知识点和具体的算法。
如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。
文章list
好了，天不早了，干点正事哇。 
你能所学到的知识点
- 动态规划基础知识
- 单序列问题
- 双序列问题
- 矩阵路径问题
- 背包问题
动态规划基础知识
运用动态规划解决问题的第一步是识别哪些问题适合运用动态规划。和运用回溯法的问题类似，使用动态规划的问题都存在若干步骤，并且每个步骤都面临若干选择。
- 如果要求列举出所有的解决，那选择用回溯法解决
- 如果求一个问题的最优解(
最大值或者最小值)，或者求问题的数目，那选择动态规划
在采用动态规划时，总是用递归的思路分析问题，即把大问题分成小问题，再把小问题的解合起来形成大问题的解。
找出描述大问题的解和小问题的解之间递归关系的状态转移方程是采用动态规划解决问题的关键所在。
如果将大问题分解成若干小问题之后，小问题相互重叠，那么直接用递归的代码实现就会存在大量重复计算。小问题之间存在重叠的部分，这是可以运用动态规划求解问题的另一个显著特点。
在用代码实现动态规划时，有两种方式
- 采用递归的代码按照从上往下的顺序求解，那么每求出一个小问题的解就缓存下来，这样下次再遇到相同的小问题就不用重复计算。
- 按照从下往上的顺序，从解决最小的问题开始，并把已经解决的小问题的解存储下来（大部分都是存储在一维数组或者二维数组中），然后把小问题的解组合起来逐步解决大问题。
爬楼梯的最小成本
题目描述：
一个数组
cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本cost[i]之后可以从i级台阶往上爬1级或2级。假设台阶至少有2级，既可以从第0级台阶出发，也可以从第1级台阶出发。请计算爬上该楼梯的最少成本。
输入：
cost = [10, 15, 20]输出：
15--> 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费 15 。
分析
- 爬上一个有多级台阶的楼梯需要若干步，每一步有两个选择，
- 既可以往上爬1级台阶，
- 也可以爬2级台阶
- 计算爬上楼梯最少成本，而不是所有的解 -- 抛弃回溯法，选择动态规划
确定状态转移方程
用f(i)表示从楼梯的第i级台阶再往上爬的最少成本。如果一个楼梯有n级台阶(台阶从0开始计数，从第0级一直到第n-1级)，由于一次可以爬1级或2级台阶，因此可以从第n-2级台阶或第n-1级台阶爬到楼梯的顶部，即f(n-1)和f(n-2)的最小值就是这个问题的最优解。
应用动态规划的第1步是找出动态转移方程，即用一个等式表示其中某一步的最优解和前面若干步的最优解的关系。(反向推理)
根据题目要求，可以一次爬1级或2级台阶，
- 既可以从第
i-1级台阶爬上第i级台阶， - 也可以从第
i-2级台阶爬上第i级台阶。
因此，从第i级台阶往上爬的最少成本应该是从第i-1级台阶往上爬的最少成本和从第i-2级台阶往上爬的最少成本的较小值再加上爬第i级台阶的成本。
用状态转移方程表示为f(i) = Math.min(f(i-1),f(i-2)) + cost[i]
上面的状态转移方程有一个隐含条件，即i大于或等于2。
- 如果
i等于0,可以直接从第0级台阶往上爬 ->f(0) = cost[0] - 如果
i等于1，可以直接从第1级台阶往上爬 ->f(1) = cost[1]
代码实现
递归代码
状态转移方程其实是一个递归的表达式，可以很方便的将它转换成递归代码。
function minCost(cost){ let len = cost.length; return Math.min(helper(cost,len -2),helper(cost,len -1)); } 复制代码
辅助函数
function helper(cost,i){ if(i<2){ // 基线条件 return cost[i] } return Math.min(helper(cost,i-2),helper(cost,i-1)) + cost[i]; } 复制代码
代码解释
- 递归函数
helper和状态转移方程相对应 - 求解
f(i)这个问题的解，依赖于求解f(i-1)和f(i-2)这两个子问题的解，由于求解f(i-1)和f(i-2)这两个子问题有重叠的部分。如果只是简单的将状态转移方程转换成递归的代码就会带来严重的效率问题。
使用缓存的递归代码
为了避免重复计算，一个常用的解决办法就是将已经求解过的问题的结果保存下来。
在每次求解一个问题之前，应先检查该问题的求解结果是否已经存在。如果问题的求解过程已经存在，则不需要重复计算，只需要从缓存中读取之前的求解结果即可。
function minCost(cost){ let len = cost.length; if(len<=2){ return Math.min(cost[0],cost[1]) } //初始化都为 0 计算之后应该是大于 0 的结果 let dp = new Array(len).fill(0); //从最上层的台阶往下走 从上到下进入递归 helper(cost,len -1,dp); return Math.min(dp[len-2],dp[len-1]); } 复制代码
辅助函数
function helper(cost,i,dp){ if(i<2){ //基线条件 dp[i] = cost[i] }else if(dp[i]==0){ helper(cost,i-2,dp); helper(cost,i-1,dp); dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i] } } 复制代码
代码解释
- 数组
dp用来保存求解每个问题结果的缓存
dp[i]用来保存f(i)的计算结果- 该数组的每个元素都初始化为
0->new Array(len).fill(0)
- 由于从每级台阶往上爬的成本都是正数，如果某个问题
f(i)之前已经求解过，那么dp[i]的缓存的结果将是一个大于0的数值。
- 只有当
dp[i]等于0时，它对应的f(i)之前还没有被求解过
- 有了缓存
dp，就能确保每个问题f(i)只需要求解一次。 - 在辅助函数中，针对
i<2的情况，是直接返回dp[i] = cost[i],但是，没有处理比较特殊的情况
- 当
cost.length ≤2时，需要做一次特殊处理。 - 直接返回它们的最小值即可
Maht.min(cost[0],cost[1])
空间复杂度为O(n)的迭代代码
也可以自下而上的解决这个过程，也就是从子问题入手，根据两个子问题f(i-1)和f(i-2)的解求出f(i)的结果。
通常用迭代的代码实现自下而上的求解过程。
function minCost(cost){ let len = cost.length; let dp = new Array(len).fill(0); dp[0] = cost[0]; dp[1] = cost[1]; for(let i =2;i<len;i++){ dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i] } return Math.min(dp[len-2],dp[len-1]) } 复制代码
代码解释
- 先求得
f(0)和f(1)的结果并保存到数组dp的前两个位置
dp[0] = cost[0];dp[1] = cost[1];
- 用一个
for循环根据状态转移方程逐一求解f(2)到f(n-1) - 时间复杂度和空间复杂度都是
O(n)
空间复杂度为O(1)的迭代代码
用一个长度为n的数组将所有f(i)的结果都保存下来。但是，在求解f(i)时只需要f(i-1)和f(i-2)的结果。 从f(0)到f(i-3)的结果其实在求解f(i)并没有任何作用。
也就是说，在求每个f(i)的时候，需要保存之前的f(i-1)和f(i-2)的结果，因此只需要一个长度为2的数组即可
function minCost(cost){ let len = cost.length; let dp = [cost[0],cost[1]]; fort(let i =2;i<len;i++){ dp[i&1] = Math.min(dp[0],dp[1])+cost[i] } return Math.min(dp[0],dp[1]); } 复制代码
代码解释
dp的长度是2，求解的f(i)的结果保存在数组下标为i&1的位置。- 可以根据
f(i-1)和f(i-2)的结果计算出f(i)的结果，并将f(i)的结果写入之前保存f(i-2)的位置。
- 用
f(i)的结果覆盖f(i-2)的结果并不会带来任何问题 - 因为，接下来求解
f(i+1)只需要f(i)的结果和f(i-1)的结果 - 不需要
f(i-2)的结果
比较4种解法
- 第一种解法在找出状态转移方程之后直接将其准换成递归代码，由于计算过程中存在大量的重复计算，时间复杂度很大
- 第二种解法在第一种解法的基础上添加了一个一位数组，用来缓存已经求解的结果。
- 有了这个长度
O(n)的数据，缓存之后就能够确保每个子问题值需要计算一次 - 时间复杂度为
O(n)
- 第三种解法时间复杂度和空间复杂度都是
O(n)。和第二种解法有两方面的不同
- 求解顺序不同： 第二种解法从大的子问题出发，采用自上而下的顺序求解；而第三种解法从子问题出发，采用自下而上的顺序求解。
- 代码实现思路不同：第二种采用递归方式实现；而第三种采用迭代方式实现。
- 第四种解法在第三种解法的基础上进一步优化空间效率，使空间下来变成
O(1)。
单序列问题
解决单序列问题，需要若干步骤，并且每个步骤都面临若干选择，需要计算解的数目或最优解。
这类题目的输入通常是一个序列，如一个一维数组或字符串。
应用动态规划解决单序列问题的关键是每一步在序列中{增加}一个元素，根据题目的特点找出该元素对应的最优解（或解的数目）和前面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程。
一旦找出了状态转移方程，只要注意避免不必要的重复计算，就能解决问题。
房屋偷盗
题目描述：
输入一个数组表示某条街道上的一排房屋内的财产的数量。如果这条街道上相邻的两栋房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取到多少财产
输入：
nums = [1,2,3,1]输出：
4偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 =
1 + 3 = 4。
分析
- 应用动态规划解决问题的关键就是在于找出转移方程。
- 用动态规划解决单序列的问题的关键在于找到序列中一个元素对应的解和前面若干元素对应的解的关系，并用状态转移方程表示。
- 假设街道上有
n幢房屋（分别用0~n-1标号），小偷从标号为0的房屋开始偷东西。
- 用
f(i)表示小偷从标号为0的房屋开始标号为i的房屋为止最多能偷取到的财物最大值 f(n-1)的值是小偷从n幢房屋中能偷取的最多财物的数量。
- 小偷在标号为
i的房屋前有两个选择
- 选择进去偷东西 - 由于有报警系统，因此他不能进入相邻的标号为
i-1的房屋内，之前他最多能偷取的财物的最大值是f(i-2),因此，如果进入标号为i的房屋并进行偷盗，他最多能偷的f(i-2)+nums[i] - 不进入标号为
i的房屋 - 那么他可以进入标号为i-1的房屋，因为此时他最多能偷取的财物数量为f(i-1)
- 在到达标号为
i的房屋时，他能偷取的财物的最大值就是两个选项的最大值
f(i) = max(f(i-2)+nums[i],f(i-1))
- 状态转移方程还有一个隐含条件，即
i大于或等于2
- 当
i等于0时，f(0) = nums[0] - 当
i等于1时，f(1)= max(nums[0],nums[1])
带缓存的递归代码
状态转移方程是一个递归的表达式。可以创建一个数组dp,它的第i个元素dp[i]用来保存f(i)的结果。
如果f(i)之前已经计算出结果，那么只需要从数组dp中读取dp[i]的值，不用在重复计算。
function rot(nums){ if(nums.length==0) return 0; let dp = new Array(nums.length).fill(-1); (function helper(nums,i,dp){ if(i ==0){ dp[i] = nums[0] }else if(i ==1){ dp[i] = Math.max(nums[0],nums[1]) }else if(dp[i]<0){ helper(nums,i -2,dp); helper(nums,i -1,dp); dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]) } })(nums,nums.length-1,dp); return dp[nums.length-1] } 复制代码
代码解释
- 函数
helper就是将状态转移方程f(i)= max(f(i-2)+nums[i],f(i-1))翻译成js的代码。 - 状态转移方程要求
i大于或等于2，因此函数helper单独处理了i分别等于0和1的特殊情况
空间复杂度为O(n)的迭代代码
递归代码是采用自上而下的处理方式，我们也可以选择使用自下而上的迭代代码。
先求出f(0)和f(1)的值，
- 然后用
f(0)和f(1)的值求出f(2) - 用
f(1)和f(2)的值求出f(3) - 依次类推，直至求出
f(n-1)
function rob(nums){ if(nums.length==0) return 0; let dp = new Array(nums.length).fill(0); dp[0] = nums[0]; if(nums.length>1){ dp[1] = Math.max(nums[0],nums[1]) } for(let i=2;i<nums.length;i++){ dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]) } return dp[nums.length-1] } 复制代码
空间复杂度为O(1)的迭代代码
在空间复杂度为O(n)的迭代代码中发现，计算dp[i]时，只需要用到dp[i-1]和dp[i-2]两个值，也就是说，只需要缓存两个值就足够了，并不需要一个长度为n的数组。
function rob(nums){ if(nums.length==0) return 0; let dp = new Array(2).fill(0); dp[0] = nums[0]; if(nums.length>1){ dp[1] = Math.max(nums[0],nums[1]) } for(let i=2;i<nums.length;i++){ dp[i&1] = Math.max(dp[(i-1)&1],dp[(i-2)&1]+nums[i]) } return dp[(nums.length-1)&1] } 复制代码
代码解释
- 数组
dp的长度为2，将f(i)的计算结果保存在数组下标为dp[i&1]的位置
f(i)和f(i-2)将保存到数组的同一个位置
- 根据
f(i-1)和f(i-2)的结果计算出f(i),然后用f(i)的结果写入数组原来保存f(i-2)的位置。 - 接下来用
f(-1)和f(i)的结果计算出f(i+1)
环形房屋偷盗
题目描述：
一条环形街道上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。计算小偷在这条街道上最多能偷取的财产的数量
输入：
nums = [1,2,3,1]输出：
4先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 =
1 + 3 = 4。
分析
- 线性街道上的房屋和环形街道上的房屋存在不同之处
- 如果
n幢房屋围成一个首尾相接的环形，那么标号为0的房屋和标号为n-1的房屋相邻。如果小偷进入这两幢房屋内偷东西就会触发报警系统。 - 这个问题和线性街道的区别在于小偷不能同时到标号为
0和n-1的两幢房屋内偷东西 - 因此将这个问题分解成两个子问题
- 求从标号为
0开始到标号为n-2结束的房屋内偷得的最多财物的数量 - 求从标号为
1开始到标号为n-1结束的房屋内偷得的最多财物的数量
代码实现
在线性街道的代码基础上做一点修改
function rob(nums){ if(nums.length ==0) return 0; if(nums.length ==1) return nums[0]; let result1 = helper(nums,0,nums.length -2); let result2 = helper(nums,1,nums.length -1); return Math.max(result1,result2) } 复制代码
辅助函数helper
function helper(nums,start,end){ let dp = new Array(2).fill(0); dp[0] = nums[start]; if(start<end){ dp[1] = Math.max(nums[start],nums[start+1]) } // 注意i的取值 for(let i= start+2;i<=end;i++){ let j = i - start; //这里是关键 dp[j&1] = Math.max(dp[(j-1)&1],dp[(j-2)&1]+nums[i]) } // 最后取值 return dp[(end- start)&1] } 复制代码
双序列问题
双序列问题的输入有两个或更多的序列，通常是两个字符串或数组。
由于输入的是两个序列，因此状态转移方程通常有两个参数，
- 即
f(i,j)- 定义第一个序列中下标从
0到i的子序列- 和第二个序列中下标从
0到j的子序列的最优解或解的个数
一旦找到了f(i,j)与
f(i-1,j-1)f(i-1,j)f(i,j-1)
的关系，问题就会迎刃而解。 
双序列的状态转移方程有两个参数，因此通常需要使用一个二维数组来保存状态转移方程的计算结果。
最长公共子序列
题目描述：
输入两个字符串，请求出它们的最长公共子序列的长度。
如果从字符串
s1中删除若干字符之后能得到字符串s2，那么字符串s2就是字符串s1的一个子序列
输入：
s1 = "abcde",s2 = "ace"输出：
3最长公共子序列是 "ace" ，它的长度为 3。
分析确定状态转移方程
- 应用动态规划解决问题的关键在于确定状态转移方程。
- 由于输入有两个字符串，因此状态转移方程有两个参数。
- 用函数
f(i,j)表示 - 第1个字符串中下标从
0到i的字符串(记为s1[0..i]) - 第2个字符串中下标从
0到j的字符串(记为s2[0..j]) - 的最长公共序列的长度
- 如果第1个字符串的长度是
m，第2个字符串的长度是n，那么f(m-1,n-1)就是问题的解 - 如果第1个字符串中下标为
i的字符(记为s1[i])与第2个字符串中下标为j(记为s2[j])的字符相同，
- 那么
f(i,j)相当于在s1[0..i-1]和s2[0..j-1]的最长公共子序列的后面添加一个公共字符。 - 也就是
f(i,j) = f(i-1,j-1)+1
- 如果字符
s1[i]与字符s2[j]不相同，则这两个字符不可能同时出现在s1[0..i]和s2[0..j]的公共子序列中。此时s1[0..i]和s2[0..j]的最长公共子序列，
- 要么是
s1[0..i-1]和s2[0..j]的最长公共子序列 - 要么是
s1[0..i]和s2[0..j-1]的最长公共子序列 - 也就是，此时
f(i,j)是f(i-1,j)和f(i,j-1)的最大值
- 那么状态转移方程为
- 当
s1[i]==s2[j],f(i,j) = f(i-1,j-1)+1 - 当
s1[i]!=s2[j],f(i,j) = max(f(i-1,j),f(i,j-1))
- 上述状态转移方程的
i或者j等于0时，即求f(0,j)或f(i,0)时可能需要的f(-1,j)或f(i,-1)的值。
f(0,j)的含义是s1[0..0]和s2[0..j]这两个字符串的最长公共子序列的长度- 即第1个字符串只包含一个下标为
0的字符，那么f(-1,j)对应的第1个子字符串再减少一个字符 - 所以第1个字符串是空字符串。
- 任意空字符串和另一个字符串的公共子序列的长度都是
0,所以f(-1,j)的值等于0
根据状态转移方程写代码
状态转移方程可以用递归的代码实现，但由于存在重叠的子问题,因此需要用一个二维数组缓存计算结果，以确保不必要的重复计算。
也可以用自下而上的方法来计算状态转移方程，这个方程可以看成一个表格的填充过程，可以用一个表格来保存
f(i,j)的计算结果。
- 先将表格中
i等于-1对应的行和j等于-1对应的列都初始化为0 - 然后按照从上到下、从左到右的顺序填充表格中的其他位置
先用一个二维数组实现这个表格，然后用一个二重循环实现从上到下、从左到右的填充顺序。
function longestCommonSubsequence(s1,s2){ let l1 = s1.length; let l2 = s2.length; // 注意行、列的长度 （l1+1/l2+1） let dp = new Array(l1+1).fill(0) .map(()=> new Array(l2+1).fill(0) ) for(let i=0;i<l1;i++){ for(let j=0;j<l2;j++){ if(s1[i]==s2[j]){ dp[i+1][j+1]= dp[i][j]+1 }else { dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]) } } } return dp[l1][l2]; } 复制代码
代码解释
- 由于表格中有
i等于-1对应的行和j等于-1对应的列，因此如果输入字符串的长度分别为m、n，那么代码中的二维数组dp的行数和列数分别是m+1和n+1
f(i,j)的值保存在dp[i+1][j+1]中
优化空间效率，只保存表格的两行
f(i,j)的值依赖于表格中
- 左上角
f(i-1,j-1)的值、 - 正上方
f(i-1,j)的值 - 同一行左边
f(i,j-1)的值
由于计算f(i,j)的值只需要使用上方一行的值和同一行左边的值，因此实际上只需要保存表格中两行就可以。
function longestCommonSubsequence(s1,s2){ let l1 = s1.length; let l2 = s2.length; if(l1<l2){ return longestCommonSubsequence(s2,s1) } //行数为2 let dp = new Array(2).fill(0) .map(()=> new Array(l2+1).fill(0) ) for(let i=0;i<l1;i++){ for(let j=0;j<l2;j++){ if(s1[i]==s2[j]){ // 处理行数 dp[(i+1)&1][j+1]= dp[i&1][j]+1; }else { // 处理行数 dp[(i+1)&1][j+1] = Math.max( dp[i&1][j+1], dp[(i+1)&1][j] ) } } } return dp[l1&1][l2] } 复制代码
代码解释
- 二维数组
dp只有两行，f(i,j)的值保存在dp[(i+1)&1][j+1]中。 - 由于数组
dp的行数是一个常数，因此此时的空间复杂度是O(min(m,n))
进一步优化空间效率，只需要一个一维数组
只需要用一个一维数组就能保存所有计算所需要的信息。这个一维数组的长度是表格的列数。（即输入字符串
s2的长度+1）。
为了让一个一维数组保存表格的两行信息。
- 一维数组的每个位置需要保存原来表格中上下两格的信息
- 即
f(i,j)和f(i-1,j)都保存在数组dp下标j+1的位置。
在计算f(i,j)之前，dp[j+1]中保存的是f(i-1,j)的值；在完成f(i,j)的计算之后，dp[j+1]被f(i,j)的值替换。
在计算f(i,j+1)时，可能还需要f(i-1,j)的值，因此在计算f(i,j)之后，不能直接用f(i,j)的值替换dp[j+1]中的f(i-1,j)的值。
可以在用f(i,j)的值替换dp[j+1]中f(i-1,j)的值之前先将f(i-1,j)的值临时保存起来。这样在下一步在计算f(i,j+1)时还能得到f(i-1,j)的值。
function longestCommonSubsequence(s1,s2){ let l1 = s1.length; let l2 = s2.length; if(l1<l2){ return longestCommonSubsequence(s2,s1) } let dp = new Array(l2+1).fill(0); for(let i=0;i<l1;i++){ let prev = dp[0]; for(let j = 0;j<l2;j++){ let cur ; if(s1[i]==s2[j]){ cur = prev +1; }else { cur = Math.max(dp[j],dp[j+1]) } prev = dp[j+1]; dp[j+1]= cur; } } return dp[l2] } 复制代码
代码解释
- 变量
prev用来保存数组中被替换的值。
- 在计算
f(i,j)之前，变量prev保存的是f(i-1,j-1)的值。 - 在计算
f(i,j)（代码中变量cur）之后，将它保存到dp[j+1]中。
- 在保存
f(i,j)之前，将保存在dp[j+1]中的值(即f(i-1,j))临时保存到变量prev中 - 下一步计算
f(i,j+1)时可以从变量prev中得到f(i-1,j) - 在代码
cur = Math.max(dp[j],dp[j+1])中
dp[j]对应的是f(i,j-1)dp[j+1]对应的是f(i-1,j)
- 由于是按照从上而下、从左到右的顺序填充表格，因此在计算
f(i,j)之前，f(i,j-1)的值已经计算出来并保存到dp[j]的位置
- 此时
f(i,j)的值还没有计算出来，因此保存在dp[j+1]中的还是f(i-1,j)的值
矩阵路径问题
这类问题通常输入是一个二维的格子，一个机器人按照一定的规则从格子的某个位置走到另一个位置，要求计算路径的条数或找出最优路径。
矩阵路径相关问题的状态转移方程通常有两个参数，即
f(i,j)的两个参数i、j通常是机器人当前到达的坐标。
需要根据路径的特点找出到达坐标(i,j)之前的位置，通常是
- 左上角
f(i-1,j-1)的值、 - 正上方
f(i-1,j)的值 - 同一行左边
f(i,j-1)的值
中的一个或多个。相应地，状态转移方程就是找出f(i,j)与f(i-1,j-1)、f(i-1,j)、f(i,j-1)的关系。
可以根据状态转移方程写出递归代码，但是一定要将f(i,j)的计算结果用一个二维数组缓存，以避免不必要的重复计算。也可以将计算所有f(i,j)看成填充二维表格的过程
路径的数目
题目描述：
一个机器人从
m×n的格子的左上角出发，它每步要么向下要么向右，直到抵达格子的右下角。请计算机器人从左上角到达右下角的路径的数目
输入：
m = 3, n = 2输出：
3从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
分析
机器人每走一步都有两个选择，
- 要么向下走，
- 要么向右走。
一个任务需要多个步骤才能完成，每步面临若干选择。题目要求计算路径的数目，而不是具体路径，选择动态规划解决该问题。
分析确定状态转移方程
- 用函数
f(i,j)表示从格子的左上角坐标为(0,0)的位置出发到达坐标为(i,j)的位置的路径数目。
- 如果格子的大小为
m×n,那么f(m-1,n-1)就是问题的解
- 当
i等于0时，机器人位于格子最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。
- 因此，
f(0,j)等于1 - 即机器人只有一种方法可以到达坐标为
f(0,j)的位置 - 即从
f(0,j-1)的位置向右走一步
- 当
j等于0时，机器人位于格子最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j为0的位置。
- 因此，
f(i,0)等于1 - 即机器人只有一种方法可以到达坐标为
(i,0)的位置 - 即从
(i-1,0)的位置向下走一步
- 当行号
i、列号j都大于0时，机器人有两种方法可以到达坐标为(i,j)的位置。
- 可以从坐标为
(i-1,j)的位置向下走一步 - 可以从坐标为
(i,j-1)的位置向右走一步 - 因此，
f(i,j)= f(i-1,j)+f(i,j-1)
根据状态转移方程写递归代码
function uniquePaths(m,n){ let dp = new Array(m).fill(0) .map(()=> new Array(n).fill(0) ) return (function helper(i,j,dp){ if(dp[i][j]==0){ if(i==0||j==0){ dp[i][j] =1; }else { dp[i][j] = helper(i-1,j,dp) + helper(i,j-1,dp) } } return dp[i][j] })(m-1,n-1,dp) } 复制代码
代码解释
- 为了避免不必要的重复计算，需要用一个二维数组缓存
f(i,j)的结果。 f(i,j)保存在dp[i][j]中
迭代代码
如果将二维数组dp看成一个表格，在初始化表格的第1行(行号为0)和第1列(列号0)之后，可以按照从左到右、从上到下的顺序填充表格的其他位置。
f(0,j)和f(i,0)的值都等于1，将表格的第1行和第1列的值都设为1- 计算第2行(行号为1)剩下的位置的值。
- 按照状态转移方程,
f(1,1)等于f(0,1)与f(1,0)之和 f(1,2)等于f(1,1)和f(0,2)之和
- 依次类推，计算剩余行数
function uniquePaths(m,n){ let dp = new Array(m).fill(0).map((item,index)=>{ if(index == 0){ // 初始化f(0,j) return new Array(n).fill(1) }else { return new Array(n).fill(0) } }); for(let i=1;i<m;i++){ dp[i][0] =1 } for(let i=1;i<m;i++){ for(let j=1;j<n;j++){ dp[i][j] = dp[i][j-1]+dp[i-1][j] } } return dp[m-1][n-1] } 复制代码
优化空间效率
在计算f(i,j)时，只需要计算用到f(i-1,j)和f(i,j-1)的值，因此只需要保存标号分别为i-1和i的两行就可以。
创建一个只有两行的二维数组dp，将f(i,j)保存在dp[i&1][j]中，那么将空间复杂度到O(n)。
还可以进一步优化空间效率，只需要创建一个一维数组dp就可以，在计算f(i,j)时需要用到f(i-1,j)和f(i,j-1)的值。接下来在计算f(i,j+1)时需要用到f(i-1,j+1)和f(i,j)的值。在计算完f(i,j)之后，就不再需要f(i-1,j)的值。（正上方的值）
在二维表格中，f(i,j)和f(i-1,j)是上下相邻的位置。由于f(i-1,j)计算出f(i,j)就不再需要，因此可以只用一个位置来保存f(i-1,j)和f(i,j)的值。
- 这个位置在计算
f(i,j)之前保存的是f(i-1,j)的值 - 计算
f(i,j)之后，保存的是f(i,j)的值
由于每个位置能够用来保存两个值，因此只需要一个一维数组就能保存表格中的两行。
function uniquePaths(m,n){ // 数组长度为列数 let dp = new Array(n).fill(1); for(let i=1;i<m;i++){ for(let j=1;j<n;j++){ dp[j] += dp[j-1] } } return dp[n-1] } 复制代码
代码解释：
dp是一个一维数组，f(i-1,j)和f(i,j)都保存在dp[j]中。- 仍然用一个二重循环按照状态转移方程计算
- 循环体内的
dp[j]+=dp[j-1]可以看成dp[j]= dp[j]+dp[j-1]
- 在赋值运算符的右边
dp[j]保存的是f(i-1,j)，dp[j-1]中保存的是f(i,j-1) - 在计算
f(i,j)之前，按照从左到右的顺序f(i,j-1)的值已经计算出来并保存在dp[j-1]中 - 用
f(i-1,j)和f(i,j-1)的值计算出f(i,j)之后将结果保存到dp[j]中
- 虽然之前保存在
dp[j]中的f(i-1,j)的值被覆盖，但这个值不在需要，因此覆盖这个值并不会出现任何问题
最小路径之和
题目描述：
给定一个包含非负整数的
m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
输入：
grid = [[1,3,1],[1,5,1],[4,2,1]]输出：
7因为路径
1→3→1→1→1的总和最小。
分析
机器人每走一步都有两个选择，
- 要么向下走，
- 要么向右走。
一个任务需要多个步骤才能完成，每步面临若干选择。题目要求计算路径的数目，而不是具体路径，选择动态规划解决该问题。
分析确定状态转移方程
- 用函数
f(i,j)表示从格子的左上角坐标为(0,0)的位置(用grid[0][0]表示)出发到达坐标为(i,j)的位置(用grid[i][j]表示)的路径的数字之和的最小值。 - 如果格子的大小为
m x n,那么f(m-1,n-1)就是问题的解 - 当
i等于0时，机器人位于格子的最上面的一行，机器人不可能从某个位置向下走一步到达一个行号i等于0的位置。
- 此时只有一条从左到右的路径，因此
f(0,j)为最上面一行从grid[0][0]开始到grid[0][j]为止所有格子的值之和
- 当
j等于0时，机器人位于格子的最左边的一列，机器人不可能从某个位置向右走一步到达一个列号j等于0的位置。
- 此时只有一条从上到下的路径，因此
f(i,0)为最左边一列从grid[0][0]开始到grid[i][0]为止所有格子的值之和
- 当行号
i、列号j都大于0时，机器人有两种方法可以到达坐标为(i,j)的位置
- 从坐标
(i-1,j)的位置向下走一步 - 从坐标
(i,j-1)的位置向右走一步 - 因此
f(i,j)= min(f(i-1,j)+f(i,j-1))+grid[i][j]
根据状态转移方程写代码
function minPathSum(grid){ const m = grid.length, n = grid[0].length // 状态定义：dp[i][j] 表示从 [0,0] 到 [i,j] 的最小路径和 const dp = new Array(m).fill(0) .map(() => new Array(n).fill(0) ) // 状态初始化 dp[0][0] = grid[0][0] // 状态转移 for (let i = 0; i < m ; i++) { for (let j = 0; j < n ; j++) { if (i == 0 && j != 0) { dp[i][j] = grid[i][j] + dp[i][j - 1] } else if (i != 0 && j == 0) { dp[i][j] = grid[i][j] + dp[i - 1][j] } else if (i != 0 && j != 0) { dp[i][j] = grid[i][j] + Math.min( dp[i - 1][j], dp[i][j - 1] ) } } } return dp[m-1][n-1] } 复制代码
优化空间效率
在计算f(i,j)时只需要用到它上面一行的f(i-1,j)，因此实际上只需要保留两行就可以。也就是说，创建一个只有两行的数组dp，将f(i,j)保存到dp[i&1][j]中即可。
还可以进一步优化空间，即只需要一个一维数组dp。在计算f(i,j)时，需要f(i-1,j)的值。
- 将
f(i-1,j)和f(i,j)保存到同一个数组dp的同一个位置dp[j]中 - 在计算
f(i,j)之前，dp[j]保存的是f(i-1,j)的值 - 用
f(i-1,j)的值，计算f(i,j)之后，将f(i,j)的值保存到dp[j]中
function minPathSum(grid){ let dp = new Array(grid[0].length).fill(0); dp[0] = grid[0][0]; for(let j=1;j<grid[0].length;j++){ dp[j] = grid[0][j] + dp[j-1] } for(let i=1;i<grid.length;i++){ dp[0] +=grid[i][0]; for(let j=1;j<grid[0].length;j++){ dp[j] = grid[i][j] + Math.min(dp[j],dp[j-1]) } } return dp[grid[0].length-1] } 复制代码
背包问题
背包问题基本描述如下：给定一组物品，每组物品都有重量和价格，在限定的总重量内如何选择才能使物品的总价格最高。
根据物品的特点，背包问题还可以进一步细分。如果每种物品只有一个，可以选择将之放入或不放入背包，那么可以将这类问题成为0-1背包问题。0-1背包问题是最基本的背包问题，其他背包问题通常可以转化为0-1背包问题
- 如果第
i种物品最多有Mi个，也就是每种物品的数量都是有限的，那么这类背包问题称为有界背包问题（也可以称为多重背包问题）。 - 如果每种物品的数量都是无限的，那么这类背包问题称为无界背包问题（也可以称为完全背包问题）。
分割等和子集
题目描述：
给定一个非空的正整数数组
nums，请判断能否将这些数字分成元素和相等的两部分
输入：
nums = [1,5,11,5]输出：
true
nums可以分割成[1, 5, 5]和[11]。
分析
如果能够将数组中的数字分成和相等的两部分，那么数组中所有数字的和(记sum)应该是一个偶数。
如果将数组中的每个数字看成物品的重量，也可以这样描述这个问题：能否选择若干物品，使它们刚好放满一个容量为t的背包？由于每个物品(数字)最多只能选择一次，因此这是一个0-1背包问题。
如果有n个物品，每步判断一个物品是否要放入背包，也就是说解决这个问题需要n步，并且每步都面临着放入或者不放入两个选择，看起来是一个能用回溯法解决的问题，但是题目中没有要求列出所有可能的方法。只要求判断是否存在放满背包的方法，所以选择用动态规划解决该问题。
分析确定状态转移方程
- 用
f(i,j)表示能否从前i个物品（物品标号分别为0，1...i-1）中选择若干物品放满容量为j的背包。
- 如果总共有
n个物品，背包的容量为t，那么f(n,t)就是问题的解
- 当判断能否从前
i个物品中选择若干物品放满容量为j的背包时，对标号为i-1的物品有两个选择
- 将标号为
i-1的物品放入背包中，如果能从前i-1个物品(物品标号分别为0,1,...i-2)中选择若干物品放满容量为j-nums[i-1]的背包（即f(i-1,j-nums[i-1])为true）,那么f(i,j)就为true - 不将标号为
i-1的物品放入背包，如果从前i-1个物品中选择若干物品放满容量为j的背包（即f(i-1,j)为true）,那么f(i,j)也为true
- 当
j等于0时，即背包的容量为0,不论有多少物品，只要什么物品都不选择，就能使选中的物品总重量为0,
- 因此
f(i,0)都为true
- 当
i等于0时，即物品的数量为0,肯定无法用0个物品来放满容量大于0的背包，
- 因此当
j大于0时，f(0,j)都为false
根据状态转移方程写递归代码
function canPartition(nums){ let sum =nums.reduce((acc,cur)=>acc+cur,0); if(sum&1==1) return false; return subsetSum(nums,sum/2) } 复制代码
辅助函数
function subsetSum(nums,target){ // 初始化为null let dp = new Array(nums.length+1).fill(0) .map(()=>new Array(target+1).fill(null)); return (function helper(nums,dp,i,j){ if(dp[i][j]===null){ if(j==0){ dp[i][j]= true; }else if(i==0){ dp[i][j] = false }else { // 不选择放入 dp[i][j]= helper(nums,dp,i-1,j); // 选择放入 if(!dp[i][j]&&j>=nums[i-1]){ dp[i][j] = helper(nums,dp,i-1,j-nums[i-1]) } } } return dp[i][j] })(nums,dp,nums.length,target) } 复制代码
代码解释
- 先求出数组
nums中所有数字之和sum,然后调用函数subsetSum判断能否从数组中选出若干数字使它们的和等于target(target为sum的一半) - 为了避免不必要的重复计算，用二维数组
dp保存f(i,j)的计算结果。 - 如果某个
dp[i][j]等于null，则表示该位置对应的f(i,j)还没有计算过
根据状态转移方程写递归代码
如果将二维数组dp看成一个表格，就可以用迭代的代码进行填充。根据状态转移方程，表格的
- 第1列(
j等于0)的所有格子都标为true - 第1行的其他格子(
i等于0并且j大于0)都标为false - 接下来从第2行(
i等于1)开始从上到下、从左到右填充表格中每个格子。
按nums = [1,5,11,5]进行数据分析：
第2行的第2个格子对应f(1,1),它表示能否从数组的前一个数字（即1）中选出若干数字使和等于1.
- 如果不选择1，那么
f(1,1)的值等于f(0,1)的值，而f(0,1)的为false - 如果选择1，此时
f(1,1)等于f(0,0)，而f(0,0)为true,因此f(1,1)为true
第2行的第3个格子对应f(1,2)，它表示能否从数组的前一个数字（即1）中选出若干数字使和等于2.
- 如果不选择1，那么
f(1,2)的值等于f(0,2)的值，而f(0,2)的为false - 如果选择1，此时
f(1,1)等于f(0,1)，而f(0,0)为false,因此f(1,2)为false
function subsetSum(nums,target){ let m = nums.length; let n = target; let dp = new Array(m+1).fill(0) .map(()=> new Array(n+1).fill(false) ); for(let i=0;i<=m;i++){ dp[i][0] = true; } for(let i=1;i<=m;i++){ for(let j=1;j<=n;j++){ dp[i][j] = dp[i-1][j]; if(!dp[i][j]&& j>=nums[i-1]){ dp[i][j] = dp[i-1][j-nums[i-1]] } } } return dp[m][n] } 复制代码
最少的硬币数量
题目描述：
给定正整数数组
conis表示硬币的面额和一个目标总额t,请计算凑出总额t至少需要的硬币数目。每种硬币可以使用任意多枚
输入：
coins = [1, 2, 5], t = 11输出：
3
11 = 5 + 5 + 1。
分析
将每种面额的硬币看成一种物品，而将目标总额看成背包的容量，那么这个问题可以等价于求将背包放满时物品的最少件数。 这里每种面额的硬币可以使用任意多次，因此这个问题不是0-1背包问题，而是一个无界背包问题（也叫完全背包问题）
分析确定状态转移方程
- 分析和解决完全背包问题的思路与
0-1背包问题的思路类似 - 用函数
f(i,j)表示用前i种硬币（coins[0...i-1]）凑出总额为j需要的硬币的最少数目。
- 当使用0枚标号为
i-1的硬币时，f(i,j)等于f(i-1,j)（用前i-1种硬币凑出总额j需要的最少硬币数目，再加上0枚标号为i-1的硬币） - 当使用1枚标号为
i-1的硬币时，f(i,j)=f(i-1,j-coins[i-1])+1(用前i-1种硬币凑出总额j-coins[i-1]需要的最少硬币数目，再加上1枚标号为i-1的硬币) - 以此类推，当使用
k枚标号为i-1的硬币时，f(i,j) = f(i-1,j-k × coins[i-1]) + k（用前i-1种硬币凑出总额j - k × coins[i-1]需要的最少硬币数目，再加上k枚标号为i-1的硬币）
- 状态转移方程为
f(i,j)=min(f(i-1,j - k × conis[i-1])+k)- (
k × conis[i-1]≤j)
- 如果硬币有
n种，目标总额为t，那么f(n,t)就是问题的解 - 当
j等于0（即总额等于0）时，f(i,0)等于0，即从前i种硬币中选出0个硬币，使总额等于0 - 当
i等于0且j大于0时，即用0种硬币凑出大于0的总额，这是不可能的
根据状态转移方程写代码
可以用不同的方法实现状态转移方程
- 转换成递归代码
- 将计算
f(i,j)看成填充一个表格并用二重循环实现 - 在②的基础上，优化空间复杂度，只使用一个一维数组就能保存所有需要的信息
function coinChane(conis,target){ let dp = new Array(target+1).fill(target+1); dp[0]= 0; for(let coin of coins){ for(let j = target;j>=-1;j--){ for(let k=1;k*coin <= j;k++){ dp[j] = Math.min(dp[j],dp[j-k*coin]+k) } } } return dp[tareget] > target ?-1 :dp[target] } 复制代码
代码解释：
- 硬币的面额是正整数，每种硬币的面额一定大于或等于1。如果能用硬币凑出总额
target，那么硬币的数目一定小于或等于target
- 用
target+1表示某个面额不能用输入的硬币凑出
另外一种思路
用函数f(i)表示凑出总额为i的硬币需要的最少数目。这个函数只有一个参数，表示硬币的总额。如果目标总额为t，那么f(t)就是整个问题的解。
为了凑出总额为i的解，有如下选择
- 在总额为
i-conis[0]的硬币中添加1枚标号为0的硬币，此时f(i)=f(i-coins[0])+1（在凑出总额为i-coins[0]的最少硬币数的基础上加1枚标号为0的硬币） - 在总额为
i-coins[1]的硬币中添加1枚标号为1的硬币，此时f(i)=f(i-coins[1])+1 - 依次类推，在总额为
i-coins[n-1]的硬币中添加1枚标号为n-1的硬币，此时f(i)等于f(i-coins[n-1])+1
状态转移方程表示为
f(i) = min(f(i-coins[j])+1)- (
coins[j]≤i)
由于状态转移方程只有1个参数，因此只需要一个一维数组就可以保存所有f(i)的计算结果
function coinChange(coins,target){ let dp = new Array(target+1).fill(0) for(let i=1;i<=target;i++){ dp[i]= target+1; for(let coin of coins){ if(i>=coin){ dp[i] = Math.min(dp[i],dp[i-coin]+1) } } } return dp[target]>target?-1:dp[target] } 复制代码
总结
通过记住一些事情来节省时间，这就是动态规划的精髓。 具体来说，如果一个问题的子问题会被我们重复利用，我们则可以考虑使用动态规划
一般来说，动态规划使用一个一维数组或者二维数组来保存状态
动态规划做题步骤
- ① 明确
dp(i)应该表示什么（二维情况：dp(i)(j)）； - ② 根据
dp(i)和dp(i-1)的关系得出状态转移方程； - ③ 确定初始条件，如
dp(0)
分为几步
- 找到“状态”和“选择”
- 明确dp数组/函数定义
- 寻找“状态”之间的关系
运用数学归纳思想解决问题
后记
分享是一种态度。
参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版
全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。
