动态规划解决最小编辑距离问题
在自然语言处理的拼写检查、生物信息学的DNA序列相似度比对等场景中，最小编辑距离是衡量两个字符串差异程度的核心指标。它表示将一个字符串通过插入、删除、替换单个字符的操作，转换成另一个字符串所需的最少操作次数。本文将基于动态规划思想，采用静态二维数组实现DP表的方式，详细讲解最小编辑距离问题的求解过程，并附上完整可运行的C++代码。
一、最小编辑距离的动态规划思路
1. 状态定义
设两个字符串分别为 word1 （长度为 m ）和 word2 （长度为 n ），定义 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小编辑次数。
2. 边界初始化
- 当 i=0 时， word1 为空字符串，转换成 word2 的前 j 个字符需要j次插入操作，即 dp[0][j] = j 。
- 当 j=0 时， word2 为空字符串，转换成 word1 的前 i 个字符需要i次删除操作，即 dp[i][0] = i 。
3. 状态转移方程
对于 word1[i-1] 和 word2[j-1] （字符串下标从0开始，DP表下标从1开始）：
- 若 word1[i-1] == word2[j-1] ：无需任何操作， dp[i][j] = dp[i-1][j-1] 。
- 若 word1[i-1] != word2[j-1] ：取删除（ dp[i-1][j] ）、插入（ dp[i][j-1] ）、替换（ dp[i-1][j-1] ）三种操作的最小次数，再加1次当前操作，即 dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1 。
二、静态二维数组实现代码
采用静态二维数组实现DP表，需提前定义数组的最大长度（如 MAX_LEN ），适用于字符串长度固定且已知的场景，内存分配更高效。
cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 定义字符串的最大长度，可根据实际需求调整
const int MAX_LEN = 1000;
// 动态规划求解最小编辑距离（静态二维数组实现DP表）
int dpEditDistance(string& word1, string& word2) {
int m = word1.size(), n = word2.size();
// 静态二维数组作为DP表，存储子问题的解
int dp[MAX_LEN + 1][MAX_LEN + 1];
// 初始化边界：word1为空时，插入j个字符得到word2前j个字符
for (int i = 0; i <= m; ++i) dp[i][0] = i;
// 初始化边界：word2为空时，删除i个字符得到word1前i个字符
for (int j = 0; j <= n; ++j) dp[0][j] = j;
// 填充DP表，求解所有子问题
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
// 字符相等，无需操作，继承子问题解
dp[i][j] = dp[i - 1][j - 1];
} else {
// 字符不等，取删除、插入、替换的最小操作数+1
dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
// dp[m][n]即为整个问题的解
return dp[m][n];
}
// 测试示例
int main() {
string word1 = "kitten";
string word2 = "sitting";
cout << "最小编辑距离：" << dpEditDistance(word1, word2) << endl;
// 输出结果：3（kitten→sitten→sittin→sitting，共3次操作）
word1 = "intention";
word2 = "execution";
cout << "最小编辑距离：" << dpEditDistance(word1, word2) << endl;
// 输出结果：5
return 0;
}
三、代码解析与测试结果
1. 静态数组优势：静态二维数组在栈上分配内存，访问速度比动态分配的二维数组/vector更快，适合字符串长度可控的场景。
2. 时间复杂度：两层循环遍历 m*n 个状态，时间复杂度为O(mn)。
3. 空间复杂度：静态二维数组占用(MAX_LEN+1) \times (MAX_LEN+1)的空间，空间复杂度为O(MAX\_LEN^2)。
4. 测试结果：
- 字符串 kitten 和 sitting 的最小编辑距离为3；
- 字符串 intention 和 execution 的最小编辑距离为5，与理论结果一致。
四、方法优劣分析
优点
- 实现简单直观，静态数组的内存访问效率高；
- DP表完整存储了所有子问题的解，可回溯查看具体的编辑操作路径。
缺点
- 静态数组的最大长度需提前定义，灵活性不足，若字符串长度超过 MAX_LEN 会导致数组越界；
- 空间开销固定，即使处理短字符串，也会占用 MAX_LEN^2 的内存。
五、拓展方向
若需要优化空间复杂度，可将二维DP表压缩为一维数组（仅保留当前行和上一行），将空间复杂度降至O(min(m,n))；若需处理超长字符串，可改用动态二维数组或 vector 实现，避免静态数组的长度限制。