[!info] related notes 动态规划 网格 DP 与双序列 DP 编辑距离

DP 模板：编辑距离

识别信号

• 两个字符串
• 插入 / 删除 / 替换
• 求最少操作次数

状态

dp[i][j] = 把 word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数

转移

if (word1[i - 1] === word2[j - 1])
    dp[i][j] = dp[i - 1][j - 1]
else
    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

模板

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

边界

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