动态规划解法-程序员充电站

一、动态规划解编辑距离的核心原理

编辑距离（Levenshtein 距离）的动态规划解法核心是用二维数组存储子问题的解，避免递归的重复计算，其核心逻辑基于：

定义dp[i][j]：表示将word1的前i个字符转换成word2的前j个字符所需的最少操作次数。
边界条件：
- dp[i][0] = i：把word1前i个字符转成空字符串，需要删除i次；
- dp[0][j] = j：把空字符串转成word2前j个字符，需要插入j次。
状态转移：
- 如果word1[i-1] == word2[j-1]（当前字符相等）：无需操作，dp[i][j] = dp[i-1][j-1]；
- 如果word1[i-1] != word2[j-1]（当前字符不等）：取「删除、插入、替换」三种操作的最小值 + 1，即：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

二、动态规划解法代码逐行解析

下面针对dpEditDistance函数逐行拆解，帮你理解每一步的作用：

int dpEditDistance(string& word1, string& word2) { // 1. 获取两个字符串的长度（m=word1长度，n=word2长度） int m = word1.size(), n = word2.size(); // 2. 定义DP表：静态二维数组，大小(MAX_LEN+1)x(MAX_LEN+1) // 为什么+1？因为dp[i][j]对应前i/j个字符，需要包含i=0/j=0的边界情况 int dp[MAX_LEN + 1][MAX_LEN + 1]; // 3. 初始化边界条件（核心！） // 边界1：word2为空，word1前i个字符转空需要删除i次 for (int i = 0; i <= m; ++i) dp[i][0] = i; // 边界2：word1为空，空字符串转word2前j个字符需要插入j次 for (int j = 0; j <= n; ++j) dp[0][j] = j; // 4. 填充DP表（核心状态转移） // 遍历word1的每个字符（i从1到m，对应前i个字符） for (int i = 1; i <= m; ++i) { // 遍历word2的每个字符（j从1到n，对应前j个字符） for (int j = 1; j <= n; ++j) { // 情况1：当前字符相等（word1[i-1]是第i个字符，因为数组从0开始） if (word1[i - 1] == word2[j - 1]) { // 无需操作，直接继承前i-1和j-1的结果 dp[i][j] = dp[i - 1][j - 1]; } else { // 情况2：当前字符不等，取三种操作的最小值+1 // dp[i-1][j]：删除word1第i个字符（操作数+1） // dp[i][j-1]：给word1插入word2第j个字符（操作数+1） // dp[i-1][j-1]：替换word1第i个字符为word2第j个字符（操作数+1） dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } // 5. 返回最终结果：word1全量转word2全量的最少操作次数 return dp[m][n]; }

三、实际执行示例（以 "horse"→"ros" 为例）

我们用代码中的测试用例word1="horse"（m=5）、word2="ros"（n=3），看 DP 表的填充过程：

步骤 1：初始化边界

i\j	0 (空)	1 (r)	2 (ro)	3 (ros)
0	0	1	2	3
1	1
2	2
3	3
4	4
5	5

步骤 2：填充 DP 表（关键节点）

i=1 (h)、j=1 (r)：h≠r→min(dp[0][1], dp[1][0], dp[0][0])+1 = min(1,1,0)+1=1→dp[1][1]=1；
i=3 (r)、j=1 (r)：r=r→dp[3][1] = dp[2][0] = 2；
i=5 (e)、j=3 (s)：e≠s→min(dp[4][3], dp[5][2], dp[4][2])+1→ 最终dp[5][3]=3（和代码输出一致）。

最终结果dp[5][3]=3，表示 "horse" 转 "ros" 最少需要 3 次操作（删除 h、删除 e、替换 s→e，或其他等价操作）。

四、动态规划解法的优化点（可选）

你提供的代码用了静态二维数组，虽然简单但有优化空间，适合新手进阶：

空间优化（一维数组）：观察状态转移可知，dp[i][j]只依赖dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]，因此可以用一维数组代替二维数组，空间复杂度从O(m∗n)降到O(min(m,n))：

int dpEditDistanceOpt(string& word1, string& word2) { int m = word1.size(), n = word2.size(); // 用一维数组，长度为较短字符串+1 if (m < n) return dpEditDistanceOpt(word2, word1); int dp[n + 1]; // 初始化边界 for (int j = 0; j <= n; ++j) dp[j] = j; // 填充一维DP for (int i = 1; i <= m; ++i) { int prev = dp[0]; // 保存dp[i-1][j-1]的值 dp[0] = i; // 对应dp[i][0] = i for (int j = 1; j <= n; ++j) { int temp = dp[j]; // 保存当前dp[j]（即dp[i-1][j]） if (word1[i-1] == word2[j-1]) { dp[j] = prev; } else { dp[j] = min(min(dp[j], dp[j-1]), prev) + 1; } prev = temp; // 更新prev为下一轮的dp[i-1][j-1] } } return dp[n]; }