思路：本题是困难题，但是在前几天那道两个字符串的删除操作的基础上，继续延续思路，难度会降低很多，我们依旧使用动态规划。dp数组的含义为dp[i][j]:表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。同样我们先进行初始化和上一题一样很明显dp[i][0]=i dp[0][j] =j 所以初始化为：

for (int i = 0; i < word1.length()+1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2.length()+1; j++) {
            dp[0][j] = j;
        }

接下来本题的核心问题来了，在遍历的时候如何推导dp数组，我们知道用word1.charAt(i-1) == word2.charAt(j-1)来进行区别判断，当相等的时候，说明次数并不需要进行增加删除或者修改操作，那么dp数组就可以直接继承上一位的值即dp[i][j] = dp[i-1][j-1];
那么当不相等的时候，我们需要进行对增加删除修改分别进行判断，选出最小的一个
当进行删除的时候 如果删除word1的一个字符，dp[i][j]=dp[i-1][j]+1，删除word2也是同理dp[i][j]=dp[i][j-1]+1. 当进行修改的时候，我们会直接把word1或者word2的一个字符修改为与另一个字符串的相应字符相同的状态，那么就和相等的情况类似了只需要加上这次修改的次数即可 即dp[i][j] = dp[i-1][j-1]+1
那么如果要进行增加字符的情况呢？实际上和删除字符的dp值是一样的，因为两个字符要不断靠齐相等，一个字符串删除字符就等价于一个字符串增加一个字符

class Solution {
    public int minDistance(String word1, String word2) {
//        dp[i][j] 表示以下标i-1为结尾的字符串word1，
//        和以下标j-1为结尾的字符串word2，
//        最近编辑距离为dp[i][j]。
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length()+1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < word2.length()+1; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i < word1.length()+1; i++) {
            for (int j = 1; j < word2.length()+1 ; j++) {
//                相等时不用操作直接继承
                if (word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
//                    从增删改中 选出最小的情况
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
        
    }
}