AcWing 902. 最短编辑距离
原题链接
简单
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String A = sc.next();
int m = sc.nextInt();
String B = sc.next();
int[][] dp = new int[1005][1005];
//初始化dp数组
for (int i = 1; i <= m; i++)
dp[0][i] = i;
for (int i = 1; i <= n; i++)
dp[i][0] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
if (A.charAt(i - 1) == B.charAt(j - 1))
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);
else
dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i][j]);
}
System.out.println(dp[n][m]);
return;
}
}