动态规划套路：

把问题层层剖析，当它变成一个字符的时候，比如 ‘a’ 和 ‘b’，这时候是不是只需要变换一次就可以实现转换了，那如果‘ab’ 和 ‘ba’ 呢，不就是在‘a’ 跟 ‘b’的基础上再进行一次变换吗（看问题需要看到点上才能解决，不能按平常思维进行顺序分析）

问题解决，既然是动态规划，那自然就有两种方法

一种是递归法，也就是自顶向下，层层解析，定义出口，最终得出答案，不过递归的缺点就是重复计算，以及栈溢出问题，不建议使用。

另一种就是 dp 数组了，定义一个二维的 dp 数组保存最少的步数，再通过前一次的步数来求出下一次的步数（动态规划最最重要的要点），首先是 dp[i][j]，代表了从 str1 的第 i 个位置到 str2 的第 j 个位置的最少步数。

既然是动态规划，那自然少不了 base case， 状态转移，只要找到状态转移自然能解

      //base  case
     for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;//str1的第 i 位走到 str2的第 0 位i
        }
        for (int j = 0; j < dp[0].length; j++) {
            dp[0][j] = j;
        }

//状态转移
//也就是从   左，  上 ，   左上    这三个位置找到最小的
//如果刚好 str1[i] == str2[j] 的时候呢，就不需要做变换，也就是不需要加一

dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                //条件，如果该位置两个字符相等，就不用加一
                if (str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }

public int minDistance(String str1, String str2){
    int m = str1.length();
    int n = str2.length();
    if (m * n == 0) return m + n;
    //初始化 dp 数组
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < dp.length; i++) {
        dp[i][0] = i;//str1的第 i 位走到 str2的第 0 位i
    }
    for (int j = 0; j < dp[0].length; j++) {
        dp[0][j] = j;
    }
    //状态转移
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            //条件，如果该位置两个字符相等，就不用加一
            if (str1.charAt(i - 1) == str2.charAt(j - 1)){
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
            }
        }
    }
    return dp[m][n];
}

总结：是一道困难题，也是动态规划中非常经典的题目，建议理解思想，慢慢吸收。