动态规划题解 | #计算字符串的编辑距离#

一开始都想到动态规划，但是想的是一维，看了别人的想法才恍然大悟

dp[i][j]代表 l1 的前 i 个字符 与 l2 的前 j 个字符的最小编辑距离

字符串的编辑距离无关方向

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String l1 = in.nextLine();
        String l2 = in.nextLine();

        boolean isL1Min = l1.length() <= l2.length();
        int minLength = isL1Min?l1.length():l2.length();

        int[][] dp = new int[l1.length()+1][l2.length()+1];
	    //初始化边界值，0个字符和任意i字符的编辑距离都是i。
        for(int i=1;i<=l2.length();i++) dp[0][i] = i;
        for(int i=1;i<=l1.length();i++) dp[i][0] = i;
	  
		//字符相同直接继承，不相同便是三种情况，（增(删)字符串1，增(删)字符串2，直接替换）
        for(int i=1;i<=l1.length();i++){
            for(int j=1;j<=l2.length();j++)
                if(l1.charAt(i-1)==l2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
        }
        System.out.print(dp[l1.length()][l2.length()]);
    }
}