题目：

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example1：
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example2：
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

---

思路：

这道题的解体思路主要是动态规划。既然是动态规划那就要明确状态数组的意义以及状态方程。

状态数组：dp[i][j]的意义为word1 0-i个字符转换到word2 0-j个字符的最小的步数。

状态方程：
第i个字符等于第j个字符的时候：

dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1))

第i个字符不等于第j个字符的时候：

dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1))

状态方程的解释：
一旦word1和word2有一个字符相等则需要比较三段字符，这里拿horse和ros来举例。horse的第四个字符和ros的第三个字符相等。

• 忽略当前的s字符，取hor转ro的代价。即dp[i-1][j-1]。
• hors转到ro的代价加一，加上的一是在转为ro的基础上插入一个s。即dp[i][j-1] + 1。
• hor转到ros的代价加一，加上的一是删除hors中的s，即dp[i-1][j] + 1。

当遍历到horse的第三个字符和ros的第三个字符时，这两个字符是不等的。因此需要取ho转到ro的代价然后加一，加上的一代表着r转换为s。

注意：dp数组的长度是word1.length * word2.length。当遍历到第i个字符的时候在dp数组中对应的是i+1。这样做的原因是在遍历初始行列的时候避免出错，dp数组的0行0列首先赋上初始值，之后就可以按照dp公式计算所有字符串转换的代价了。因为之前做的时候如果遇到orr转rt的情况赋初始值会很困难，比如orr转r, o到r为1， or到r为1，orr到r为2, 很难发现规律。

horse转ros的全过程：

horse转ros的过程

---

代码：

public int minDistance(String word1, String word2) {
        if((word1 == null || word2 == null) && (word1.length() == 0 || word2.length() == 0))
            return 0;
        if(word1 == null || word1.length() == 0)
            return word2.length();
        if(word2 == null || word2.length() == 0)
            return word1.length();
        int result = 0;
        int [][] dp = new int [word1.length() + 1][word2.length() + 1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0] = i;
        }
        for(int j=0;j<=word2.length();j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
}