题解 | #双序列型DP#

import java.util.* ;
public class Main{
    public static void main(String...args) {
        Scanner sc = new Scanner(System.in) ;
        while(sc.hasNextLine()) {
            String s1 = sc.nextLine() ;
            String s2 = sc.nextLine() ;
            System.out.println(dp(s1,s2)) ;
        }
    }
    public static int dp(String str1 , String str2) {
        char[] a1 = str1.toCharArray() ;
        char[] a2 = str2.toCharArray() ;
        int len1 = a1.length ;
        int len2 = a2.length ;
        //f[i][j]表示str1的前i个字符与str2的前j个字符的最小编辑距离
        int f[][] = new int[len1+1][len2+1] ;
        for(int i = 0 ; i < len1+1 ; i ++) {
            for(int j = 0 ; j < len2+1 ; j ++) {
                //空串和任何非空串的最小编辑距离都是非空串的长度
                if(i == 0 || j == 0) {
                    f[i][j] = i+j ;
                    continue ;
                }
                //转移方程
                //f[i][j]=min{f[i][j-1]+1,f[i-1][j-1]+1,f[i-1][j]+1,f[i-1][j-1]|a1[i-1]=a2[j-1]}
                f[i][j] = Math.min(f[i][j-1]+1,f[i-1][j-1]+1) ;
                f[i][j] = Math.min(f[i][j],f[i-1][j]+1) ;
                if(a1[i-1] == a2[j-1]) {
                    f[i][j] = Math.min(f[i][j],f[i-1][j-1]) ;
                }
            }
        }
        return f[len1][len2] ;
    }
}