当前位置：首页 > news >正文

【算法训练-动态规划五】【二维DP问题】编辑距离

news 2025/9/21 16:52:22

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【动态规划】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
在这里插入图片描述

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

编辑距离【HARD】

终于又来到一道看了很久的高频题目这里

题干

搞定了一系列的简单题，来个编辑距离练练手
在这里插入图片描述

解题思路

原题解地址，解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前移动，缩小问题的规模

设两个字符串分别为 rad 和 apple，为了把 s1 变成 s2，算法会这样进行
在这里插入图片描述

暴力递归

base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度。对于每对儿字符 s1[i] 和 s2[j]，可以有四种操作：

if s1[i] == s2[j]:啥都别做（skip）i, j 同时向前移动
else:三选一：插入（insert）删除（delete）替换（replace）

有这个框架，问题就已经解决了。读者也许会问，这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁

int minDistance(String s1, String s2) {int m = s1.length(), n = s2.length();// i，j 初始化指向最后一个索引return dp(s1, m - 1, s2, n - 1);
}// 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {// base caseif (i == -1) return j + 1;if (j == -1) return i + 1;if (s1.charAt(i) == s2.charAt(j)) {return dp(s1, i - 1, s2, j - 1); // 啥都不做}return min(dp(s1, i, s2, j - 1) + 1,    // 插入dp(s1, i - 1, s2, j) + 1,    // 删除dp(s1, i - 1, s2, j - 1) + 1 // 替换);
}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));
}

情况一：什么都不做

if s1[i] == s2[j]:return dp(s1, i - 1, s2, j - 1); # 啥都不做
# 解释：
# 本来就相等，不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)

如果 s1[i] != s2[j]，就要对三个操作递归了

情况二：插入操作

dp(s1, i, s2, j - 1) + 1,    # 插入
# 解释：
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
# 别忘了操作数加一

在这里插入图片描述
插入操作

情况三：删除操作

dp(s1, i - 1, s2, j) + 1,    # 删除
# 解释：
# 我直接把 s[i] 这个字符删掉
# 前移 i，继续跟 j 对比
# 操作数加一

在这里插入图片描述

情况四：替换操作

dp(s1, i - 1, s2, j - 1) + 1 # 替换
# 解释：
# 我直接把 s1[i] 替换成 s2[j]，这样它俩就匹配了
# 同时前移 i，j 继续对比
# 操作数加一

在这里插入图片描述
a字符被替换为p字符

int dp(i, j) {dp(i - 1, j - 1); // #1dp(i, j - 1);     // #2dp(i - 1, j);     // #3
}

对于子问题 dp(i-1, j-1)，如何通过原问题 dp(i, j) 得到呢？有不止一条路径，比如 dp(i, j) -> #1 和 dp(i, j) -> #2 -> #3。一旦发现一条重复路径，就说明存在巨量重复路径，也就是重叠子问题

动态规划

接下来用DP table来优化一下，降低重复子问题，首先明确 dp 数组的含义，dp 数组是一个二维数组，长这样
在这里插入图片描述
有了之前递归解法的铺垫，应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和之前的 dp 函数类似

替换操作：word1的0~i-1位置与word2的0~j-1位置的字符都相同,只是当前位置的字符不匹配,进行替换操作后两者变得相同dp[i-1][j-1] 表示需要进行替换操作才能转到dp[i][j]，所以此时dp[i][j]=dp[i-1][j-1]+1(这个加1代表执行替换操作)
删除操作: 若此时word1的0~i-1位置与word2的0~j位置已经匹配了,此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)和word2的0~j位置匹配,因此此时dp[i][j]=dp[i-1][j]+1(这个加1代表执行删除操作)
插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配，此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,所以此时dp[i][j]=dp[i][j-1]+1(这个加1代表执行插入操作)

有了之前递归解法的铺垫，应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base case，dp[i][j] 的含义和之前的 dp 函数类似

int dp(String s1, int i, String s2, int j)
// 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离

dp 函数的 base case 是 i, j 等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位

dp[i-1][j-1]
// 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离

既然 dp 数组和递归 dp 函数含义一样，也就可以直接套用之前的思路写代码，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解

int minDistance(String s1, String s2) {int m = s1.length(), n = s2.length();// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]int[][] dp = new int[m + 1][n + 1];// base case for (int i = 1; i <= m; i++)dp[i][0] = i;for (int j = 1; j <= n; j++)dp[0][j] = j;// 自底向上求解for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i-1) == s2.charAt(j-1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1,dp[i - 1][j - 1] + 1);}}}// 储存着整个 s1 和 s2 的最小编辑距离return dp[m][n];
}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));
}

代码实现

给出代码实现基本档案

基本数据结构：数组
辅助数据结构：无
算法：动态规划
技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Solution
{// 编辑距离，返回两个字符串操作的最小距离public int minDistance(String word1, String word2){// 1 入参校验if(word1.length() < 1 && word2.length() < 1){return 0;}// 2 定义行列长度，word1作为竖，word2作为行int m = word1.length();int n = word2.length();// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i+1][j+1]int[][] dp = new int[m + 1][n + 1];// 4 初始化base casefor(int i = 1; i <= m; i++){dp[i][0] = i;}for(int j = 1; j <= n; j++){dp[0][j] = j;}// 5 状态转移方程:自底向上求解，从头开始比较，i=0和j=0的位置初始化为基本操作数for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = minCompare(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);}}}return dp[m][n];}private int minCompare(int a, int b, int c){return Math.min(a, Math.min(b, c));}
}