给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
解题思路：动态规划
(1) 定义dp数组
dp[i][j]：word1[0:i]子串，和word2[0:j]子串 相同时，需要的最小步数
(2) 状态转移方程
● 当 word1[i] == word2[j] 时，dp[i][j] = min( dp[ i-1 ][ j-1 ], min( dp[ i-1 ][j]+1, dp[i][ j-1 ]+1 ) );
● 当 word1[i] != word2[j] 时，dp[i][j] = min( dp[ i-1 ][ j-1 ]+2, min( dp[ i-1 ][j]+1, dp[i][ j-1 ]+1 ) );
(3) 初始化
从状态转移方程可以看出，dp[i][j] 需要依赖 dp[ i-1 ][j]、dp[i][ j-1 ]、dp[ i-1 ][ j-1 ]。
所以要单独考虑 i == 0，及 j == 0 的情况：
● dp[0][0] = ( (word1[i] == word2[j])? 0 : 2 )
● 当 i == 0，j != 0 时，dp[i][j] = min( j, dp[i][ j-1 ]+1 )（不包括 i == 0，且 j == 0 的情况）
● 当 i != 0，j == 0 时，dp[i][j] = min( i, dp[ i-1 ][j]+1 ) （不包括 i == 0，且 j == 0 的情况）
(4) 遍历顺序
从上到下，从左到右
(5) 举例：略
class Solution {
public int minDistance(String word1, String word2) {
// dp[i][j]：word1[0:i]子串，和word2[0:j]子串 相同时，需要的最小步数
int[][] dp = new int[word1.length()][word2.length()];
for(int i=0; i<word1.length(); i++){
for(int j=0; j<word2.length(); j++){
if(i == 0 && j == 0) dp[i][j] = (word1.charAt(i) == word2.charAt(j) ? 0 : 2); // 两个都要删除
else if(i == 0) dp[i][j] = ((word1.charAt(i) == word2.charAt(j)) ? j : dp[i][j-1]+1);
else if(j == 0) dp[i][j] = ((word1.charAt(i) == word2.charAt(j)) ? i : dp[i-1][j]+1);
else{
if(word1.charAt(i) == word2.charAt(j)) dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]) + 1);
else dp[i][j] = Math.min(dp[i-1][j-1] + 2, (Math.min(dp[i-1][j], dp[i][j-1]) + 1));
}
}
}
return dp[word1.length()-1][word2.length()-1];
}
}
