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

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String a = sc.nextLine();
            String b = sc.nextLine();
            int[][] dp = new int[a.length()+1][b.length()+1];  //定义动规数组

            for(int i=1; i<=a.length(); i++){  // 初始化
                dp[i][0] = i;
            }
            for(int i=1; i<=b.length(); i++){  // 初始化
                dp[0][i] = i;
            }
            for(int i=1; i<=a.length(); i++){
                for(int j=1; j<=b.length(); j++){
                    //第一种情况，a[i]==b[j]，这种情况下，我们不需要进行编辑，dp[i][j]=dp[i-1][j-1] 
                    //第二种情况，a[i]!=b[j]，如果两个字符不相等，我们有三种处理方式：
                    //1、替换字符串b，编辑距离为dp[i-1][j-1]+1；
                    //2、插入一个字符与其相等，则编辑距离为dp[i-1][j]+1；
                    //3、删除该字符，编辑距离为dp[i][j-1]+1，三者取其小即可
                    if(a.charAt(i-1)==b.charAt(j-1)){  //第一种情况
                        dp[i][j] = dp[i-1][j-1];
                    }else{  //第二种情况
                        //替换字符的意思就是将 j 指向的字符和 i 指向的字符通过替换的方式配对成功，所以两列分别减去最后一个字符后得到的最优解 + 1 即：dp[i-1][j-1]+1
                        //插入一个字符的意思是将 i指向的字符和新增字符配对成功，所以第一列的数据还有i-1,第二列数据j，最优解 dp[i-1][j] +1
                        //删除一个字符的意思，将 j 指向的字符删除，dp[i][j - 1] + 1
                        dp[i][j] = Math.min(dp[i-1][j]+1, Math.min(dp[i-1][j-1]+1, dp[i][j-1]+1));  //状态转移方程
                    }
                }
            }
            System.out.println(dp[a.length()][b.length()]);
        }
    }
}