别来无恙
Search K

Appearance

算法刷题总结（二） ​

动态规划 ​

动态规划是一种将复杂问题分解为更简单的子问题的算法设计方法。它通过存储子问题的解来避免重复计算，从而提高效率。

动态规划的应用场景 ​

  1. 动规基础问题：斐波那契、爬楼梯
  2. 背包问题
  3. 打家劫舍问题
  4. 股票买卖问题
  5. 子序列问题：最长递增子序列、字符串编辑最小距离
  6. 区间DP、概率 DP（难度过高不考虑）

动态规划思路拆解5步 ​

  1. DP 数组以及下标 的含义
  2. 递推公式（状态转移方程）
  3. DP 数组如何初始化以及边界条件
  4. 遍历顺序（从小到大还是从大到小、背包问题先遍历背包还是先遍历物品）
  5. 打印DP数组的变化过程（作为调试依据）

背包问题 ​

背包类型 ​

  1. 01 背包：n 种物品，每种物品只能选一次
  2. 完全背包：n 种物品，每种物品可以选多次
  3. 多重背包(不考虑)：n 种物品，每种物品个数各不相同

01 背包 ​

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

基本信息如下： 01 背包

dp数组的含义 ​

dp[i][j] : 下标 0-i 的物品任取放入容量为 j 的背包中，能获得的最大价值

递推公式 ​

01 背包因为物品只能放入 1 次，所以可以先遍历每个物品，每个物品的状态为放入背包和不放入背包（也可以先遍历背包容量，从小到大依次递减，判断是否放入对应容量大小物品）。此时状态转移方程为：

js
// 不放入物品 i，背包重量和价值不变: dp[i][j] = dp[i-1][j]
// 放入物品 i，背包重量减去物品 i 重量，价值增加物品 i 价值: dp[i][j] = dp[i-1][j-weight[i]] + value[i]
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

dp数组初始化和遍历顺序 ​

由递推公式可知：dp[i][j] 的状态依赖于 i-1 和 j-weight[i]， 也就是依赖左边和上边，所以遍历顺序应该从左到右，从上到下。确保每个状态都能在使用前被计算出来。此时我们需要先初始化第一行状态:

  1. dp[0][j] = j >= weight[0] ? value[0] : 0 : 取决于背包容量 j 是否能放入物品 0（因为同个物品只能放入 1 次所以最大价值为物品 0 的价值），最大价值也为 0（不能放入）或者 value[0]（能放入） 。 此时dp 数组初始化情况如下： DP 数组初始化

二维DP 数组模版 ​

js
// 1. 初始化二维数组为 0
// 2. 因为依赖上一行 i-1 的状态，所以需要初始化第一行。
// 遍历背包容量，从大于等于物品0 开始，背包价值为物品0 的价值
for (let j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
// weight数组的大小 就是物品个数
// 01 背包二维数组两个 for 循环先遍历物品和先遍历背包都是可以的。不影响状态转移
for(let i = 0; i < weight.length; i++) { // 遍历物品
   for(let j = 0; j <= bagweight; j++) { // 遍历背包容量
      if (j < weight[i]) {
         // 背包容量小于物品 i 的重量，不能放入物品 i
         // 此时最大价值和不放入物品 i 一样,不考虑放入物品 i ，避免数组下标 j - weight[i]为负数
         dp[i][j] = dp[i - 1][j]
      }else{
         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
      };

   }
}

dp数组降维 ​

  1. 由递推公式可知：不论是放入物品 i 还是不放入物品 i ，dp[i][j] 的状态都只依赖于 dp[i-1] 的状态，所以可以将 dp 数组由二维数组降维为一维数组。只维护 dp[i-1] 层的状态即可。
  2. 此时 dp[j] 的含义即为：容量为 j 的背包能获得的最大价值。
  3. 递推公式变为：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])。 此时状态依赖 dp[j-weight[i]]，所以我们要考虑 dp[0] 的状态（这里 dp[0] 初始化状态表示背包容量 0，物品数量也为 0，也就是二维数组dp[0][0]的情况，并非是说考虑放入物品 0 第一行的最大价值，因为后续遍历时会不断更新dp[0]（j - weight[i]为 0） ，此时才是放入物品 0 时（对应二维第一行）的状态。）。
  4. 一维数组模版
js
// 1. 初始化一维数组为 0
let dp = new Array(bagweight + 1).fill(0);
// 2. 遍历背包容量，一维数组中我们只需要考虑 dp[0]的状态。非 0 下标由于 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])且背包是倒序遍历的，不依赖 dp[i-1] 的状态，所以我们不需要像二维一样先初始化物品 0 的情况。
dp[0] = 0; // 当背包容量为 0 时，放满背包的最大价值为 0，所以这里也可以省略。但是算排列组合问题时这里需要初始化 dp[0] = 1;，表示背包容量为0的方法数为 1，即不放物品
// 3. 遍历物品，一维数组只能先遍历物品再遍历背包。否则背包的最大价值记录的都只会是某一个物品的最大价值了
for(let i = 0; i < weight.length; i++) { // 遍历物品
   // 4. 遍历背包容量，为了保证遍历背包容量时上一层的状态dp[j - weight[i]]不被覆盖，需要从大到小遍历背包容量。也可以理解倒序可以保证每个物品只被添加一次。
   for(let j = bagweight; j >= weight[i]; j--) { 
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
   }
}

01背包解决排列组合 ​

有n件物品和一个最多能背重量为w 的背包。每个物品可以放入 1 次，求放满背包的方法有几种。

二维DP数组版本 ​

  1. 二维 DP 数组的含义：dp[i][j] 表示 0-i 个物品放入容量为 j 的背包的总方法。
  2. 递推公式：dp[i][j] = dp[i-1][j] + dp[i-1][j-weight[i]]。即不放入物品 i 时放满背包容量 j 的方法数 + 放入物品 i时放满背包容量（此时背包容量为 j-weight[i] ）的方法数。
  3. dp 数组初始化和遍历顺序：由递推公式可知，我们需要先初始化最上边行的状态（同 01 背包基础）。
    • 初始化第一行：dp[0][i]状态：当且仅当背包容量i等于物品 0 的重量时，放满背包的方法数为 1（即此时放入物品 0），否则为 0。
  4. 二维 DP 数组模版
js
// 1. 初始化二维数组为 0
let n = weight.length
let dp = new Array(n).fill(0).map(() => new Array(bagweight + 1).fill(0));
// 2. 初始化第一行和第一列
// 初始化第一行，
// 不放物品 0
dp[0][0] = 1;
// 放物品 0，防止数组下标溢出，加个判断
if (weight[0] <= bagweight) {
   // 只考虑物品 0 的情况下，当且仅当背包容量等于物品 0 的重量时，放满背包的方法数为 1，否则为 0
    dp[0][weight[0]] = 1;
}

// 3. 遍历物品和背包容量，二维数组先遍历物品还是背包都可以，背包遍历顺序正反也都可以
for (let i = 1; i < n; i++) { // 遍历物品
    for (let j = 1; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) {
            dp[i][j] = dp[i - 1][j]; // 背包容量小于物品 i 的重量，不能放入物品 i
        } else {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - weight[i]]; // 放入物品 i 和不放入物品 i 的方法数
        }
    }
}

一维DP数组版本 ​

  1. 一维 DP 数组的含义：dp[j] 表示放入容量为 j 的背包的总方法数。
  2. 递推公式：dp[j] = dp[j] + dp[j-weight[i]]。即不放入物品 i 时放满背包容量 j 的方法数 + 放入物品 i时放满背包容量（此时背包容量为 j-weight[i] ）的方法数。
  3. dp 数组初始化和遍历顺序：由递推公式可知，我们需要先初始化dp[0]的状态（背包容量为 0，不放任何物品）
  4. 一维数组递推公式也可以这样理解，dp[j] 的总方法拆解为：
    • 背包里面包含物品 0 的方法：dp[j - weight[0]](放入物品 0 时的方法数)
    • 背包里面包含物品 1 的方法：dp[j - weight[i]] (放入物品 1 时的方法数)
    • ...
    • 背包里面包含物品 n 的方法：dp[j - weight[n]] (放入物品 n 时的方法数)
    • 总的方法则是以上所有方法的和：dp[j] += dp[j - nums[i]];
  5. 一维 DP 数组模版
js
// 1. 初始化一维数组为 0
let dp = new Array(bagweight + 1).fill(0);
// 2. 考虑背包容量为 0，物品 0 个的情况，即不放任何物品此时重量为 0，为 1 种方法（ 01 背包基础的差异点）
dp[0] = 1; 
// 3. 遍历物品和背包容量，一维数组先遍历物品再遍历背包
for (let i = 0; i < weight.length; i++) { // 遍历物品
   // 4. 遍历背包容量，为了保证遍历背包容量时上一层的状态dp[j - weight[i]]不被覆盖，需要从大到小遍历背包容量。也可以理解倒序可以保证每个物品只被添加一次。
   for (let j = bagweight; j >= weight[i]; j--) { 
      dp[j] += dp[j - weight[i]];
   }
}

完全背包 ​

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包模板（1 维数组） ​

js
// 1. 初始化一维数组为 0
let dp = new Array(bagweight + 1).fill(0);
// 2. 考虑背包容量为 0，物品 0 个的情况
dp[0] = 0;
// 3. 遍历物品和背包容量，一维数组先遍历物品(完全背包问题也可以先遍历背包再遍历物品)
for (let i = 0; i < weight.length; i++) { 
   // 4. 遍历背包容量，完全背包物品可以被重复加入，所以要利用当前行的状态，也就是背包容量要正序遍历（与 01 背包的区别点）
   for (let j = weight[i]; j <= bagweight; j++) { 
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
   }
}

完全背包解决排列组合问题 ​

有n件物品和一个最多能背重量为w 的背包。每个物品可以放入多次，求放满背包的方法有几种。

  1. 这里一维递推公式和 01 一样，都是 dp[j] += dp[j - weight[i]]。
  2. 初始化时: 需要考虑 dp[0] 状态（一般 dp[0] = 1）
  3. 遍历顺序: 需要注意的是求方法数是排列还是组合：
    • 如果是组合问题（即物品放入顺序不同也属于同一种方法），则需要先遍历物品再遍历背包容量，此时才能保证 dp[j] 的状态是只会按照物品顺序依次更新的（遍历物品 0，更新 dp[j]，遍历物品 1 ,再更新 dp[j]，能保证物品 1 的状态是在物品 0 之后的，也就变相保证了物品顺序只会有物品 0、物品 1 的放入方法）。
    • 如果是排列问题（即物品放入顺序不同属于不同方法），则需要先遍历背包容量再遍历物品，根据背包容量 j 的逐渐增大，物品会频繁多次放入，第一次容量为 0 时循环物品 0 状态在物品 1 前更新，但是从容量 1 开始，物品 1 也会去更新物品 0 的状态。（也就会有先放物品 0 后放物品 1，和先放物品 1 再放物品 0 的两种放入方法）。
  4. 完全背包排列组合问题一维 DP 数组模版：
js
// 1. 初始化一维dp数组
let dp = new Array(bagweight + 1).fill(0);
// 2. 考虑背包容量为 0，物品 0 个的情况
dp[0] = 1; // 不放任何物品时，放满背包的方法数为 1
// 3. 组合问题先遍历物品后遍历背包容量
for (let i = 0; i < weight.length; i++) { // 依次遍历物品，所以这里只会有先物品 0、物品 1 的放入顺序。不会有先物品 1、物品 0 的情况
   // 4. 遍历背包容量。注意排列问题先遍历背包时，下标应该从 0 开始（此时 weight[i]也是未确定的）。
   for (let j = weight[i]; j <= bagweight; j++) { 
      dp[j] += dp[j - weight[i]];
   }
}

爬楼梯思维解决完全背包排列问题 ​

  1. 思维转变：我们要爬背包重量层楼梯，每次能爬的步数在物品中选择，判断最后爬到楼顶用多少中方式（或者能否爬到楼顶）。
  2. 爬楼梯到达楼顶总方式递推公式： 在爬到第 j - climb[i] 层楼梯的前提下，我们再爬 climb[i] 步即可到达楼顶。所以 dp[j] 的状态依赖于 dp[j - climb[i]] 的状态。我们需要考虑 dp[0] 的初始化，一般 dp[0] = 1，表示到达起始位置第 0 层的方式有 1 种，即不怕任何楼梯。此时递推公式为：dp[j] += dp[j - climb[i]]。
  3. 爬楼梯能否到达楼顶递推公式：dp[j] = dp[j - climb[i]]。即在能爬到第 j - climb[i] 层楼梯的前提下，我们再爬 weight[i] 步即可到达楼顶。
  4. 爬楼梯问题一维 DP 数组模版：
js
// 1. 初始化一维dp数组，到达楼顶位置为 stairs +1，如果是能否抵达问题。则要初始化为 false
let dp = new Array(stairs + 1).fill(0);
// 2. 考虑在初始位置 0 层的情况 ，如果是能否抵达问题，则dp[0]初始化为 true
dp[0] = 1; // 不爬即可抵达为 1 种方法
// 3. 遍历楼梯
for (let j = 0; j <= stairs; j++) { // 遍历每个楼梯
   // 4. 遍历每次可以爬的步数 climb[i]
   for (let i = 0; i < climb.length; j++) { 
      let climb = climb[i]; // 当前爬的步数
      if (j <= climb) continue; // 如果当前楼梯层数小于爬的步数，则不能到达
      dp[j] += dp[j - climb[i]]; // 爬到第 j 层楼梯的方式等于爬到第 j - climb[i] 层楼梯的方式

      // 楼顶能否抵达问题：
      // if (!dp[j - climb[i]]) continue; // 如果前面楼梯没有到达方式，则不能到达当前层
      // dp[j] = dp[j - climb[i]]; // 如果前面楼梯有到达方式，则当前层楼梯的方式等于前面楼梯的方式
   }
}

return dp[stairs]; // 返回到达楼顶的方式 or 能否到达楼顶

打家劫舍问题 ​

  1. dp[i] 的含义: 表示考虑（注意：这里是考虑，并不是一定偷第 i 个）0-i 个房屋时，所能偷的最大金额。
  2. 递推公式：第 i 个房屋有两种选择：偷或者不偷。
    • 如果偷第 i 个房屋，则不能偷第 i-1 个房屋，此时最大金额为 dp[i-2] + nums[i]（即前 i-2 个房屋的最大金额 + 第 i 个房屋的金额，这里 dp[i-2] 不一定代表 i-2 的房屋会偷，但是dp[i-2]时 i-1 的房屋一定不会偷，因为下标根本没有考虑到 i-1）。
    • 如果不偷第 i 个房屋，则最大金额为 dp[i-1]（同理，不偷 i，这里 dp[i-1]并不代表一定偷 i-1）。
    • 所以递推公式为：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  3. 注意： 从上面的递推公式可以，i 的状态依赖于 i-1 和 i-2 的状态，在树形房屋时，想要获取 dp[i-2] 的状态并不方便(i-1 可以通过 node.left 和 node.right 获取)，所以此 dp[i] 的含义定义和公式并不通用。

打家劫舍通用模板 ​

  1. 通用 dp[i] 的含义：表示考虑到第 0-i 个房屋时的状态，返回值为（偷 i 时最大金额，不偷 i 时最大金额）。如果求 i 所能偷的最大金额，则返回值为 max(偷，不偷)，这里不偷不一定小于偷，有可能不偷第 i 个，选择偷 i-1个。
  2. 递推公式：第 i 个房屋时的状态：
    • 偷 i 最大金额: 不偷 i-1 + 第 i 个房屋金额，即 dp[i][0] = dp[i-1][1] + nums[i]
    • 不偷 i 最大金额为 : max(偷 i-1,不偷 i-1)，即 dp[i][1] = max(dp[i-1][0], dp[i-1][1])
    • 此时考虑 i 的最大金额为 max(dp[i][0], dp[i][1])
  3. 通过将偷和不偷分别存储，可以将 i 的状态转为只依赖 i-1 的状态。所以在树形房屋的情况下，dp[node] 的转态可以表示为：
    • 偷 node: 偷 node + 不偷 node.left + 不偷 node.right，即 dp[node][0] = node.val + dp[node.left][1] + dp[node.right][1]
    • 不偷 node: node.left偷不偷取最大 (不一定偷 left，可能偷 left 的孩子) + node.right偷不偷取最大，即 dp[node][1] = max(dp[node.left][0],dp[node.left][1]) + max(dp[node.right][0],dp[node.right][1])
    • 此时考虑node 的最大金额为 max(dp[node][0], dp[node][1])

买卖股票问题 ​

买卖股票基础问题 ​

  1. dp 定义：
    • dp[i][0]：第 i 天持有股票的最高金额
    • dp[i][1]：第 i 天不持有股票的最高金额
  2. 递归公式：
    • 从前面持有股票继承过来，或者第 i 天买入： dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
    • 前面就已经卖出，或者第 i 天卖出(如果有手续费，则卖出时减去手续费 fee)： dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
    • 第 i 天最大利润： profit = dp[i][1];(不持有股票的现金一定比持有股票的现金多)
  3. 初始化：
    • dp[0][0] = -prices[0];
    • dp[0][1] = 0;
  4. 遍历顺序：
    • 从递归公式可知，dp[i] 的状态依赖 dp[i-1]，所以下标 1 开始从前往后遍历。

买卖股票至多 k 次问题 ​

  1. k为 2 时 dp 定义：
    • dp[i][0]：第 i 天第一次持有股票的最高金额
    • dp[i][1]：第 i 天第二次持有股票的最高金额
    • dp[i][2]：第 i 天第一次不持有股票的最高金额
    • dp[i][3]：第 i 天第二次不持有股票的最高金额
  2. 递归公式：
    • 第一次持有股票：dp[i][0] = max(dp[i-1][0], -prices[i]);
    • 第二次持有股票：dp[i][1] = max(dp[i-1][1], dp[i-1][2] - prices[i]);
    • 第一次不持有股票：dp[i][2] = max(dp[i-1][2], dp[i-1][0] + prices[i]);
    • 第二次不持有股票：dp[i][3] = max(dp[i-1][3], dp[i-1][1] + prices[i]);
  3. 需要注意的时 dp 数组初始化：
    • dp[0][0] = -prices[0];
    • dp[0][1] = -prices[0]; （这里可以理解为第一天买卖然后又买入，所以是 -prices[0] 而不是 0）
    • dp[0][2] = 0; (同理当天买卖所以金额为 0)
    • dp[0][3] = 0;
  4. 遍历顺序：同买卖股票基础
  5. 最终最大利润为 max(dp[i][2], dp[i][3])，因为第二次卖出一定包含第一次卖出了，所以也可以直接返回 dp[i][3]。
  6. 第k次通用模版：
rust
pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
   if prices.len() == 1 {
      return 0;
   }

   // 1. 定义 DP 数组：dp[i][0..k]:第 1..k 次持有股票的金额，dp[i][k..2k]:第 1..k 次不持有股票的最高金额。
   let mut dp = vec![vec![0; 2 * k as usize]; prices.len()];
   // 2. 初始化第一天时持有状态的金额
   dp[0][0..k as usize].fill(-prices[0]);

   for i in 1..prices.len() {
      for j in 0..k as usize {
         // 第 i 天第 j 次持有: max(i-1 天持有, i-1 天第 j-1 次不持有 - prices[i])
         // 第 i 天第 j 次不持有：max(i-1天不持有, i-1 天第 j 次持有 + prices[i])
         let k = k as usize;
         // 第 j 次持有
         if j == 0 {
            dp[i][j] = dp[i - 1][j].max(-prices[i]);
         } else {
            dp[i][j] = dp[i - 1][j].max(dp[i - 1][j - 1 + k] - prices[i]);
         }
         // 第 j 次不持有
         dp[i][j + k] = dp[i - 1][j + k].max(dp[i - 1][j] + prices[i]);
      }
   }

   // 最后一次不持有
   return dp[prices.len() - 1][2 * k as usize - 1];
}

买卖股票包含冷冻期 ​

  1. dp 定义：
    • dp[i][0]：第 i 天持有股票的最高金额
    • dp[i][1]：第 i 天不持有股票的最高金额
  2. 递归公式：
    • 持有股票：
      1. 冷冻期为 k 天，则前 k 天只能买入一次：dp[k][0] = max(dp[i-1][0], -prices[k])
      2. 超过 k 天后, 继承前面持有或者第 i - 1 - k 天卖出时状态买入（k 为冷冻期）： dp[i][0] = max(dp[i-1][0], dp[i-1-k][1] - prices[i]);
    • 不持有股票：dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
    • 第 i 天最大利润：profit = dp[i][1];
  3. 初始化：
    • dp[0][0] = -prices[0];
    • dp[0][1] = 0;
  4. 模版：
rust
pub fn max_profit(prices: Vec<i32>) -> i32 {
   if prices.len() == 1 {
      return 0;
   }

   // 1. 定义DP
   let mut dp = vec![[0; 2]; prices.len()];

   // 2. 初始化 DP
   dp[0][0] = -prices[0];

   for i in 1..prices.len() {
      // 持有：分为两种情况
      // 前 k 天持有：前一天持有或者今天第一次买入
      // 超过 k 天后，继承前面持有或者第 i - 1 - k 天卖出时状态买入（k 为冷冻期）
      if i <= k {
         // 不能从前一天不持有状态流转，因为有冷冻期
         dp[i][0] = dp[i - 1][0].max(-prices[i]);
      } else {
         dp[i][0] = dp[i - 1][0].max(dp[i - 1 - k][1] - prices[i]);
      }
      // 不持有
      dp[i][1] = dp[i - 1][1].max(dp[i - 1][0] + prices[i]);
   }

   return dp[prices.len() - 1][1];
}

子序列问题 ​

  1. 需要注意 DP 数组的两种经典含义:
    • dp[i][j]含义 1 : 前 i 个元素 和前 j 个元素所形成的最优解。对于子序列相邻无关问题来说，含义 1用【选或不选】思考，例如 0-1 背包问题或者最长公共子序列 LCS；
    • dp[i][j]含义 2: 以下标i为结尾 和 以下标j为结尾所形成的最优解。对于子数组问题和子序列相邻相关来说，一般用含义2【枚举选哪个】思考，方便“拼接”，例如最大子数组和问题、最长递增子序列 LIS问题。
    • 为了方便处理 dp[i][0] 和dp[0][j] 状态时下标 i-1 越界，也可以将 DP 定义为前 i-1 个元素 、以下标 i-1 为结尾。
  2. 递推公式：从含义 1 和含义 2 的角度出发，思考如何将当前状态转化为前一个状态。
    • 含义 1 的递推公式一般是通过选或不选当前元素来转化为前一个状态；
    • 含义 2 的递推公式一般是通过枚举当前元素和前一个元素的关系来转化为前一个状态。
    • 这两者含义区别在于：不选当前元素时，含义 1 不需要考虑前一个元素的状态，而含义 2 则需要考虑当前元素和前一个元素的状态转移
  3. DP 数组初始化和遍历顺序
    • 如果没有定义为 i-1，那么遍历时单独处理 i 或 j 为 0 的情况，因为此时没有前一个状态可以继承。
  4. 最优解：
    • 含义 1：因为是区间，所以 dp[i][j] 一定包含前面的最优解，直接返回最后一个状态即可
    • 含义 2：不是区间，最优解存在于过程任何一个状态中，所以用单独一个变量在生成状态过程中比较并修改最大值。

编辑距离问题 ​

给你两个单词 s1 和 s2， 请返回将 s1 转换成 s2 所使用的最少操作数。

  1. DP 定义：本题是属于删与不删（选或不选）问题，因此 DP 定义为区间定义
    • dp[i+1][j+1]：表示 s1 前 i 个字符转为 s2 前 j 个字符的最小编辑距离。
  2. 递推公式：
    • s1[i] == s2[j]: dp[i+1][j+1] = dp[i][j]
    • s1[i] != s2[j]: dp[i+1][j+1] = min(dp[i+1][j],dp[i][j+1],dp[i][j]) + 1
      1. s1插入字符：相当于删除一个 s2字符，dp[i+1][j+1] = dp[i+1][j] + 1
      2. s1删除字符：移除一个 s1 字符，dp[i+1][j+1] = dp[i][j+1] + 1
      3. 替换字符：相当于插入一个和 s2 相等的字符，接着同时删除该字符（一个步骤），此时状态为 dp[i+1][j+1] = dp[i][j] + 1
  3. DP 数组初始化和遍历顺序：
    • 初始化：dp[i][0] = i， dp[0][j]=j，表示将 s1 前 i 个字符转为 s2 前 0 个字符需要 i 次删除，将 s1 前 0 个字符转为 s2 前 j 个字符需要 j 次插入。
  4. 最优解：dp[s1.length][s2.length]，表示将 s1 转换为 s2 的最小编辑距离。
  5. 模版：
rust
pub fn min_distance(word1: String, word2: String) -> i32 {
   let word1: Vec<char> = word1.chars().collect();
   let word2: Vec<char> = word2.chars().collect();

   let mut dp = vec![vec![500; word2.len() + 1]; word1.len() + 1];
   // 初始化 DP[i][0] 和 DP[0][j]
   for i in 0..=word1.len() {
      dp[i][0] = i;
   }
   for j in 0..=word2.len() {
      dp[0][j] = j;
   }

   // 遍历 DP 数组
   for i in 0..word1.len() {
      for j in 0..word2.len() {
         dp[i + 1][j + 1] = if word1[i] == word2[j] {
            dp[i][j]
         } else {
            dp[i][j + 1].min(dp[i + 1][j]).min(dp[i][j]) + 1
         }
      }
   }

   return dp[word1.len()][word2.len()] as i32;
}

图论 ​

后续更新...