最短编辑距离用二维DP数组dpi实现，表示word1前i字符转word2前j字符的最少操作数；初始化dp0=j、dpi=i；递推时字符相等则dpi=dpi-1，否则取删、插、替三者最小值加1。
在 java 中用数组实现最短编辑距离（levenshtein distance），核心是构建一个二维 dp 数组 dp[i][j]，表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数（插入、删除、替换）。空间和逻辑都可控，适合理解算法本质。
初始化二维 DP 数组
设 word1 长度为 m，word2 长度为 n，申请 int[m+1][n+1] 数组：
-
dp[0][j] = j：空字符串变word2前j字符，只能靠j次插入 -
dp[i][0] = i：word1前i字符变为空字符串，只能靠i次删除
填表逻辑：逐行逐列递推
对每个 i ∈ [1, m] 和 j ∈ [1, n]：
- 若
word1.charAt(i-1) == word2.charAt(j-1)，则dp[i][j] = dp[i-1][j-1]（无需操作） - 否则取三种操作的最小值加 1：
-
dp[i-1][j] + 1（删word1[i-1]） -
dp[i][j-1] + 1（在word1末尾插word2[j-1]） -
dp[i-1][j-1] + 1（将word1[i-1]替换为word2[j-1]）
-
完整可运行示例代码
// 注意：索引从 0 开始，字符串下标需 -1
public static int levenshteinDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
<pre class="brush:php;toolbar:false;">// 初始化边界
for (int i = 0; i <= m; i++) dp[i][0] = 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.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
Math.min(dp[i - 1][j] + 1, // 删除
dp[i][j - 1] + 1), // 插入
dp[i - 1][j - 1] + 1 // 替换
);
}
}
}
return dp[m][n];}
立即学习“Java免费学习笔记（深入）”；
小技巧：空间优化到一维数组（可选）
因每行只依赖上一行，可用两个一维数组（prev 和 curr）或仅用一个数组滚动更新：
- 维护
int[] dp = new int[n + 1] - 每次迭代前保存
dp[j-1]（即左上角值），用临时变量记录上一轮的dp[j] - 适合内存敏感场景，但初学建议先掌握二维写法
