[!info] related notes 算法面试题型 MOC 动态规划 网格 DP 与双序列 DP

编辑距离

题目链接：https://leetcode.cn/problems/edit-distance/

题意

给你两个字符串 word1 和 word2，可以对 word1 做三种操作：插入、删除、替换。求最少操作数。

状态

dp[i][j] 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符所需的最少操作数。

转移

如果最后一个字符相同：

dp[i][j] = dp[i - 1][j - 1]

否则考虑三种操作：

• 删除：dp[i - 1][j] + 1
• 插入：dp[i][j - 1] + 1
• 替换：dp[i - 1][j - 1] + 1

所以：

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

边界

• dp[i][0] = i
• dp[0][j] = j

样例

word1 = "horse", word2 = "ros"

一种变法：

• horse -> rorse（替换）
• rorse -> rose（删除）
• rose -> ros（删除）

最少操作数是 3。

JavaScript

var minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                ) + 1;
            }
        }
    }

    return dp[m][n];
};

易错点

• 第一行、第一列初始化不能漏
• 插入 / 删除 / 替换三种操作的来源状态容易写混