题目：
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的全过程：
代码：
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()];
}
