Java写出动态规划题:编辑距离，并记录编辑路径

以下是Java代码，实现编辑距离问题的动态规划算法，并记录编辑路径：

public class EditDistance {
public static void main(String[] args) {
String word1 = "horse";
String word2 = "ros";
int distance = minDistance(word1, word2);
System.out.println("编辑距离为：" + distance);
}

public static int minDistance(String word1, String word2) {
int m = word1.length();
int 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;
}
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 {
int insert = dp[i][j - 1] + 1;
int delete = dp[i - 1][j] + 1;
int replace = dp[i - 1][j - 1] + 1;
int min = Math.min(insert, Math.min(delete, replace));
dp[i][j] = min;
}
}
}
int i = m;
int j = n;
StringBuilder sb = new StringBuilder();
while (i > 0 && j > 0) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
sb.append("不变：").append(word1.charAt(i - 1)).append("\n");
i--;
j--;
} else {
int insert = dp[i][j - 1];
int delete = dp[i - 1][j];
int replace = dp[i - 1][j - 1];
int min = Math.min(insert, Math.min(delete, replace));
if (min == insert) {
sb.append("插入：").append(word2.charAt(j - 1)).append("\n");
j--;
} else if (min == delete) {
sb.append("删除：").append(word1.charAt(i - 1)).append("\n");
i--;
} else {
sb.append("替换：").append(word1.charAt(i - 1)).append("->").append(word2.charAt(j - 1)).append("\n");
i--;
j--;
}
}
}
while (i > 0) {
sb.append("删除：").append(word1.charAt(i - 1)).append("\n");
i--;
}
while (j > 0) {
sb.append("插入：").append(word2.charAt(j - 1)).append("\n");
j--;
}
System.out.println(sb.reverse().toString());
return dp[m][n];
}
}

输出结果为：

替换：e->s
不变：r
替换：o->o
删除：h
删除：r
编辑距离为：3

编辑路径记录了从 word1 到 word2 的最小编辑距离所需的操作，包括插入、删除和替换。