JS算法之动态规划

JavaScript/前端
376
0
0
2023-01-17
前端工程化_知识点精讲
上一篇
Google Chrome不仅仅是浏览器
下一篇
❝如果不能避免被剥削的命运，就要提高自己被剥削的价值。 ❞

大家好，我是「柒八九」。

今天，我们继续探索JS算法相关的知识点。我们来谈谈关于「动态规划」的相关知识点和具体的算法。

如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。

好了，天不早了，干点正事哇。

img

你能所学到的知识点

❝
  1. 动态规划基础知识
  2. 单序列问题
  3. 双序列问题
  4. 矩阵路径问题
  5. 背包问题

❞

动态规划基础知识

运用动态规划解决问题的第一步是识别哪些问题适合运用动态规划。和运用回溯法的问题类似，「使用动态规划的问题都存在若干步骤，并且每个步骤都面临若干选择」。

  • 如果要求列举出「所有」的解决，那选择用「回溯法」解决
  • 如果求一个问题的「最优解」(最大值或者最小值)，或者求问题的「数目」，那选择「动态规划」

在采用动态规划时，总是用「递归」的思路分析问题，即「把大问题分成小问题，再把小问题的解合起来形成大问题的解」。

❝找出描述大问题的解和小问题的解之间「递归关系的状态转移方程」是采用动态规划解决问题的关键所在。 ❞

如果将大问题分解成若干小问题之后，小问题「相互重叠」，那么「直接用递归的代码」实现就会存在「大量重复计算」。小问题之间存在重叠的部分，这是可以运用动态规划求解问题的另一个显著特点。

在用代码实现动态规划时，有两种方式

❝
  1. 采用「递归」的代码按照「从上往下」的顺序求解，那么每求出一个小问题的解就「缓存」下来，这样下次再遇到相同的小问题就不用重复计算。
  2. 按照「从下往上」的顺序，「从解决最小的问题开始」，并把已经解决的小问题的解存储下来（大部分都是存储在一维数组或者二维数组中），然后把小问题的解组合起来逐步解决大问题。

❞

爬楼梯的最小成本

题目描述：

❝一个数组cost的所有数字都是正数，它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本，在支付了成本cost[i]之后可以从i级台阶往上爬1级或2级。 假设台阶至少有2级，既可以从第0级台阶出发，也可以从第1级台阶出发。请计算爬上该楼梯的「最少」成本。 输入：cost = [10, 15, 20] 输出：15 --> 最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。 ❞

分析

  1. 爬上一个有多级台阶的楼梯需要「若干步」，每一步有「两个选择」，
  • 既可以往上爬1级台阶，
  • 也可以爬2级台阶
  1. 计算爬上楼梯「最少」成本，而不是所有的解 -- 抛弃回溯法，选择「动态规划」

确定状态转移方程

用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];
}

代码解释

  1. 「递归函数」helper和状态转移方程相对应
  2. 求解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]
  }
  
}

代码解释

  1. 数组dp用来保存求解每个问题结果的缓存
  • dp[i]用来保存f(i)的计算结果
  • 该数组的每个元素都初始化为0 -> new Array(len).fill(0)
  1. 由于从每级台阶往上爬的成本都是「正数」，如果某个问题f(i)之前已经求解过，那么dp[i]的缓存的结果将是一个大于0的数值。
  • 只有当dp[i]等于0时，它对应的f(i)「之前还没有被求解过」
  1. 有了缓存dp，就能确保每个问题f(i)只需要求解一次。
  2. 在辅助函数中，针对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])
}

代码解释

  1. 先求得f(0)和f(1)的结果并保存到数组dp的「前两个位置」
  • dp[0] = cost[0];
  • dp[1] = cost[1];
  1. 用一个for循环根据状态转移方程逐一求解f(2)到f(n-1)
  2. 时间复杂度和空间复杂度都是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]);
}

代码解释

  1. dp的长度是2，求解的f(i)的结果保存在数组下标为i&1的位置。
  2. 可以根据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种解法

  1. 第一种解法在找出状态转移方程之后直接将其准换成「递归代码」，由于计算过程中存在大量的重复计算，时间复杂度很大
  2. 第二种解法在第一种解法的基础上「添加了一个一位数组」，用来缓存已经求解的结果。
  • 有了这个长度O(n)的数据，缓存之后就能够「确保每个子问题值需要计算一次」
  • 时间复杂度为O(n)
  1. 第三种解法时间复杂度和空间复杂度都是O(n)。和第二种解法有两方面的不同
  2. 「求解顺序不同」：第二种解法从大的子问题出发，采用「自上而下」的顺序求解；而第三种解法从子问题出发，采用「自下而上」的顺序求解。
  3. 「代码实现思路不同」：第二种采用「递归」方式实现；而第三种采用「迭代」方式实现。
  4. 第四种解法在第三种解法的基础上进一步「优化空间效率」，使空间下来变成O(1)。

单序列问题

解决单序列问题，需要「若干步骤，并且每个步骤都面临若干选择，需要计算解的数目或最优解」。

这类题目的输入通常是「一个序列」，如一个一维数组或字符串。

❝应用动态规划解决单序列问题的关键是「每一步在序列中{增加}一个元素，根据题目的特点找出该元素对应的最优解（或解的数目）和前面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程」。 ❞

一旦找出了状态转移方程，只要注意避免不必要的重复计算，就能解决问题。

房屋偷盗

题目描述：

❝输入一个数组表示某条街道上的一排房屋内的财产的数量。如果这条街道上「相邻」的两栋房屋被盗就会自动触发报警系统。请计算小偷在这条街道上「最多」能偷取到多少财产 输入：nums = [1,2,3,1] 输出：4 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。 ❞

分析

  1. 应用动态规划解决问题的关键就是在于找出「转移方程」。
  2. 用动态规划解决「单序列的问题」的关键在于找到序列中「一个元素对应的解和前面若干元素对应的解的关系」，并用状态转移方程表示。
  3. 假设街道上有n幢房屋（分别用0~n-1标号），小偷从标号为0的房屋开始偷东西。
  • 用f(i)表示小偷从标号为0的房屋开始标号为i的房屋为止最多能偷取到的财物最大值
  • f(n-1)的值是小偷从n幢房屋中能偷取的最多财物的数量。
  1. 小偷在标号为i的房屋前有「两个选择」
  2. 「选择进去偷东西」 - 由于有报警系统，因此他不能进入相邻的标号为i-1的房屋内，之前他「最多能偷取的财物的最大值是f(i-2)」,因此，如果进入标号为i的房屋并进行偷盗，他最多能偷的f(i-2)+nums[i]
  3. 「不进入标号为i的房屋」 - 那么他可以进入标号为i-1的房屋，因为此时他「最多能偷取的财物数量为f(i-1)」
  4. 在到达标号为i的房屋时，他能偷取的财物的最大值就是「两个选项的最大值」
  • f(i) = max(f(i-2)+nums[i],f(i-1))
  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]
}

代码解释

  1. 函数helper就是将状态转移方程f(i)= max(f(i-2)+nums[i],f(i-1))翻译成js的代码。
  2. 状态转移方程要求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]
}

代码解释

  1. 数组dp的长度为2，将f(i)的计算结果保存在数组下标为dp[i&1]的位置
  • 「f(i)和f(i-2)将保存到数组的同一个位置」
  1. 根据f(i-1)和f(i-2)的结果计算出f(i),然后用f(i)的结果写入数组原来保存f(i-2)的位置。
  2. 接下来用f(-1)和f(i)的结果计算出f(i+1)

环形房屋偷盗

题目描述：

❝一条「环形街道」上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。计算小偷在这条街道上「最多」能偷取的财产的数量 输入：nums = [1,2,3,1] 输出：4 先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。 ❞

分析

  1. 「线性街道」上的房屋和「环形街道」上的房屋存在不同之处
  2. 如果n幢房屋围成一个「首尾相接」的环形，那么标号为0的房屋和标号为n-1的房屋相邻。如果小偷进入这两幢房屋内偷东西就会触发报警系统。
  3. 这个问题和「线性街道」的区别在于「小偷不能同时到标号为0和n-1的两幢房屋内偷东西」
  4. 因此「将这个问题分解成两个子问题」
  5. 求从标号为0开始到标号为n-2结束的房屋内偷得的最多财物的数量
  6. 求从标号为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)与

  1. f(i-1,j-1)
  2. f(i-1,j)
  3. f(i,j-1)

的关系，问题就会迎刃而解。

img

双序列的状态转移方程有两个参数，因此通常需要使用一个「二维数组来保存状态转移方程的计算结果」。

最长公共子序列

题目描述：

❝输入两个字符串，请求出它们的「最长」公共子序列的长度。 如果从字符串s1中「删除若干字符」之后能得到字符串s2，那么字符串s2就是字符串s1的一个子序列 输入：s1 = "abcde", s2 = "ace" 输出：3 最长公共子序列是 "ace" ，它的长度为 3。 ❞

分析确定状态转移方程

  1. 应用动态规划解决问题的关键在于确定状态转移方程。
  2. 由于输入有两个字符串，因此状态转移方程有两个参数。
  • 用函数f(i,j)表示
  • 第1个字符串中下标从0到i的字符串(记为s1[0..i])
  • 第2个字符串中下标从0到j的字符串(记为s2[0..j])
  • 的最长公共序列的长度
  1. 如果第1个字符串的长度是m，第2个字符串的长度是n，那么f(m-1,n-1)就是问题的解
  2. 如果第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
  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)的「最大值」
  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))
  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)的计算结果。 ❞
  1. 先将表格中i等于-1对应的行和j等于-1对应的列都初始化为0
  2. 然后按照「从上到下、从左到右」的顺序填充表格中的其他位置

「先用一个二维数组实现这个表格，然后用一个二重循环实现从上到下、从左到右的填充顺序」。

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];
}

代码解释

  1. 由于表格中有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]
}

代码解释

  1. 二维数组dp只有两行，f(i,j)的值保存在dp[(i+1)&1][j+1]中。
  2. 由于数组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]
}

代码解释

  1. 变量prev用来保存数组中被替换的值。
  • 在计算f(i,j)之前，变量prev保存的是f(i-1,j-1)的值。
  • 在计算f(i,j)（代码中变量cur）之后，将它保存到dp[j+1]中。
  1. 在保存f(i,j)之前，将保存在dp[j+1]中的值(即f(i-1,j))临时保存到变量prev中
  2. 下一步计算f(i,j+1)时可以从变量prev中得到f(i-1,j)
  3. 在代码cur = Math.max(dp[j],dp[j+1])中
  • dp[j]对应的是f(i,j-1)
  • dp[j+1]对应的是f(i-1,j)
  1. 由于是按照「从上而下、从左到右」的顺序填充表格，因此在计算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 条路径可以到达右下角。
  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

❞

分析

机器人每走一步都有「两个选择」，

  • 要么向下走，
  • 要么向右走。

「一个任务需要多个步骤才能完成，每步面临若干选择」。题目要求计算路径的数目，而不是具体路径，选择「动态规划」解决该问题。

分析确定状态转移方程

  1. 用函数f(i,j)表示从格子的左上角坐标为(0,0)的位置出发到达坐标为(i,j)的位置的「路径数目」。
  • 如果格子的大小为m×n,那么f(m-1,n-1)就是问题的解
  1. 当i等于0时，机器人位于格子「最上面的一行」，机器人不可能从某个位置「向下走一步」到达一个「行号」i等于0的位置。
  • 因此，f(0,j)等于1
  • 即机器人「只有一种方法」可以到达坐标为f(0,j)的位置
  • 即「从f(0,j-1)的位置向右走一步」
  1. 当j等于0时，机器人位于格子「最左边的一列」，机器人不可能从某个位置「向右走一步」到达一个「列号」j为0的位置。
  • 因此，f(i,0)等于1
  • 即机器人「只有一种方法」可以到达坐标为(i,0)的位置
  • 即「从(i-1,0)的位置向下走一步」
  1. 当行号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)
}

代码解释

  1. 为了避免不必要的重复计算，需要用一个「二维数组缓存f(i,j)的结果」。
  2. 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]
}

代码解释：

  1. dp是一个一维数组，f(i-1,j)和f(i,j)都保存在dp[j]中。
  2. 仍然用一个二重循环按照状态转移方程计算
  3. 循环体内的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]中
  1. 虽然之前保存在dp[j]中的f(i-1,j)的值被覆盖，但这个值不在需要，因此覆盖这个值并不会出现任何问题

最小路径之和

题目描述：

❝给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为「最小」。

img

输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 因为路径 1→3→1→1→1 的总和最小。 ❞

分析

机器人每走一步都有「两个选择」，

  • 要么向下走，
  • 要么向右走。

「一个任务需要多个步骤才能完成，每步面临若干选择」。题目要求计算路径的数目，而不是具体路径，选择「动态规划」解决该问题。

分析确定状态转移方程

  1. 用函数f(i,j)表示从格子的左上角坐标为(0,0)的位置(用grid[0][0]表示)出发到达坐标为(i,j)的位置(用grid[i][j]表示)的「路径的数字之和的最小值」。
  2. 如果格子的大小为m x n,那么f(m-1,n-1)就是问题的解
  3. 当i等于0时，机器人位于格子的「最上面的一行」，机器人不可能从某个位置「向下走一步」到达一个行号i等于0的位置。
  • 此时只有一条「从左到右」的路径，因此f(0,j)为「最上面一行从grid[0][0]开始到grid[0][j]为止所有格子的值之和」
  1. 当j等于0时，机器人位于格子的「最左边的一列」，机器人不可能从某个位置「向右走一步」到达一个列号j等于0的位置。
  • 此时只有一条「从上到下」的路径，因此f(i,0)为「最左边一列从grid[0][0]开始到grid[i][0]为止所有格子的值之和」
  1. 当行号i、列号j都大于0时，机器人有两种方法可以到达坐标为(i,j)的位置
  2. 从坐标(i-1,j)的位置「向下走一步」
  3. 从坐标(i,j-1)的位置「向右走一步」
  4. 因此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步」，并且每步都面临着放入或者不放入「两个选择」，看起来是一个能用「回溯法」解决的问题，但是题目中没有要求列出所有可能的方法。只要求判断是否存在放满背包的方法，所以选择用「动态规划解决」该问题。

分析确定状态转移方程

  1. 「用f(i,j)表示能否从前i个物品（物品标号分别为0，1...i-1）中选择若干物品放满容量为j的背包」。
  • 如果总共有n个物品，背包的容量为t，那么f(n,t)就是问题的解
  1. 当判断能否从「前i个物品」中选择若干物品放满容量为j的背包时，对标号为i-1的物品有「两个选择」
  2. 「将标号为i-1的物品放入背包中」，如果能从前i-1个物品(物品标号分别为0,1,...i-2)中选择若干物品放满容量为j-nums[i-1]的背包（即f(i-1,j-nums[i-1])为true）,那么f(i,j)就为true
  3. 「不将标号为i-1的物品放入背包」，如果从前i-1个物品中选择若干物品放满容量为j的背包（即f(i-1,j)为true）,那么f(i,j)也为true
  4. 「当j等于0时，即背包的容量为0」,不论有多少物品，「只要什么物品都不选择，就能使选中的物品总重量为0」,
  • 因此f(i,0)都为true
  1. 「当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)
}

代码解释

  1. 先求出数组nums中所有数字之和sum,然后调用函数subsetSum判断能否从数组中选出若干数字使它们的和等于target(target为sum的一半)
  2. 为了避免不必要的重复计算，用二维数组dp保存f(i,j)的计算结果。
  3. 如果某个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背包问题，而是一个「无界背包问题」（也叫完全背包问题）

分析确定状态转移方程

  1. 分析和解决「完全背包问题」的思路与0-1背包问题的思路类似
  2. 「用函数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的硬币）
  1. 状态转移方程为
  • f(i,j)=min(f(i-1,j - k × conis[i-1])+k)
  • (k × conis[i-1]≤j)
  1. 如果硬币有n种，目标总额为t，那么f(n,t)就是问题的解
  2. 当j等于0（即总额等于0）时，f(i,0)等于0，即从前i种硬币中选出0个硬币，使总额等于0
  3. 当i等于0且j大于0时，即用0种硬币凑出大于0的总额，这是不可能的

根据状态转移方程写代码

可以用不同的方法实现状态转移方程

  1. 转换成递归代码
  2. 将计算f(i,j)看成填充一个表格并用二重循环实现
  3. 在②的基础上，优化空间复杂度，只使用一个一维数组就能保存所有需要的信息
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. 硬币的面额是正整数，每种硬币的面额一定大于或等于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]
}

总结

❝通过记住一些事情来节省时间，这就是动态规划的精髓。具体来说，如果一个问题的子问题会被我们重复利用，我们则可以考虑使用动态规划 ❞

一般来说，动态规划使用一个一维数组或者二维数组来保存状态

动态规划做题步骤

  1. ① 明确 dp(i) 应该表示什么（二维情况：dp(i)(j)）；
  2. ② 根据 dp(i)和 dp(i-1) 的关系得出状态转移方程；
  3. ③ 确定初始条件，如 dp(0)
❝分为几步
  1. 找到“状态”和“选择”
  2. 明确dp数组/函数定义
  3. 寻找“状态”之间的关系

❞

运用「数学归纳思想」解决问题

后记

「分享是一种态度」。

参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版

「全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。」

前端工程化_知识点精讲
上一篇
Google Chrome不仅仅是浏览器
下一篇