最短编辑距离用二维DP数组dpi实现，表示word1前i字符转word2前j字符的最少操作数；初始化dp0=j、dpi=i；递推时字符相等则dpi=dpi-1，否则取删、插、替三者最小值加1。
在
java
中用数组实现最短编辑距离（levenshtein distance），核心是构建一个二维 dp 数组
，表示将
的前
个字符转换为
的前
个字符所需的最少操作数（插入、删除、替换）。空间和逻辑都可控，适合理解算法本质。
初始化二维 DP 数组
设
长度为
，
长度为
，申请
数组：
：空字符串变
前
字符，只能靠
次插入
：
前
字符变为空字符串，只能靠
次删除
填表逻辑：逐行逐列递推
对每个
和
：
若
，则
（无需操作）
否则取三种操作的最小值加 1：
（删
）
（在
末尾插
）
（将
替换为
）
完整可运行示例代码
// 注意：索引从 0 开始，字符串下标需 -1
}
Eclipse导入Android或其他的JAVA项目的正确方法 WORD版
本文档主要讲述的是Eclipse导入Android或其他的JAVA项目的正确方法；希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看
下载
立即学习
“
Java免费学习笔记（深入）
”；
小技巧：空间优化到一维数组（可选）
因每行只依赖上一行，可用两个一维数组（
和
）或仅用一个数组滚动更新：
维护
每次迭代前保存
（即左上角值），用临时变量记录上一轮的
适合内存敏感场景，但初学建议先掌握二维写法
dp[i][j]word1iword2jword1mword2nint[m+1][n+1]dp[0][j] = jword2jjdp[i][0] = iword1iii ∈ [1, m]j ∈ [1, n]word1.charAt(i-1) == word2.charAt(j-1)dp[i][j] = dp[i-1][j-1]dp[i-1][j] + 1word1[i-1]dp[i][j-1] + 1word1word2[j-1]dp[i-1][j-1] + 1word1[i-1]word2[j-1]public static int levenshteinDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化边界
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];prevcurrint[] dp = new int[n + 1]dp[j-1]dp[j]