题解 | #计算字符串的编辑距离#

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] A = in.nextLine().toCharArray();
        char[] B = in.nextLine().toCharArray();
        int[][] DP = new int[A.length + 1][B.length + 1];
        DP[0][0] = 0;
        for (int i = 0; i <= A.length; i++) {
            for (int j = 0; j <= B.length; j++) {
                if (i != 0 && j != 0) {
                    DP[i][j] = i + j;
                    DP[i][j] = Math.min(DP[i][j], DP[i - 1][j] + 1);
                    DP[i][j] = Math.min(DP[i][j], DP[i][j - 1] + 1);
                    DP[i][j] = Math.min(DP[i][j],
                                        DP[i - 1][j - 1] + (A[i - 1] == B[j - 1] ? 0 : 1));
                } else if (i != 0) {
                    DP[i][j] = i;
                } else if (j != 0) {
                    DP[i][j] = j;
                }
            }
        }
        System.out.println(DP[A.length][B.length]);
    }
}