今天又在lintCode上面做了一道动态规划的题了，不知道是不是因为自己太久没有做题了，所以感觉没什么思路了。不要颓废！在这里督促自己！
题意：
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
插入一个字符
删除一个字符
替换一个字符
样例：
给出 work1="mart" 和 work2="karma"
返回 3
1.解题思路
这道题是典型的动态规划的题，也是比较简单的动态规划的题，在这里记录一下，一是要求自己不要松懈，二是弥补自己在动态规划上的不足。
我们在这道题上，处理每一个字符无非就是3种操作，增加字符、删除字符、替换字符。
首先，我们定义一个dp[word1.length() + 1][word2.length() + 1],其中dp[i][j]表示的意思就是，word1前i个字符变成word2前j个字符需要的步数。然后，我们分三种情况来谈论：
(1).增加字符
假设word1的前i个字符到word2的前j - 1个字符已经转成了，也就是说dp[i][j - 1]已经被计算出来了，此时我们需要计算的是从 i 到j 需要的步数。可知dp[i][j] = dp[i][j - 1] + 1，我们只需要再增加一个word2[j]字符就行了。
(2).删除字符
假设word1的前i - 1个字符到word2的前j - 1字符已经转了， 也就是说dp[i - 1][j]已经被计算出来了，此时我们需要计算的是dp[i][j]的值。可知dp[i ][j] = dp[i - 1][j] + 1,直接删除第i个字符就行了。
(3).替换字符
替换字符分为两种情况，一个是word1[i] = word2[j]时，当前的dp[i][j] = dp[i - 1][j - 1]即可，因为word1[i] == word2[j]，我们不需要进行任何的操作；而当word1[i] != word2[j]时，当前的dp[i][j] = dp[i - 1][j - 1] + 1,因为我们需要替换当前的字符。
2.代码
public int minDistance(String word1, String word2) {
int dp[][] = new int[word1.length() + 1][word2.length() + 1];
for (int i = 0; i < word1.length() + 1; i++) {
// 从i个字符变成0个字符，需要i步（删除）
dp[i][0] = i;
}
for (int i = 0; i < word2.length() + 1; i++) {
// 当从0个字符变成i个字符，需要i步(增加)
dp[0][i] = i;
}
for (int i = 1; i < word1.length() + 1; i++) {
for (int j = 1; j < word2.length() + 1; j++) {
//当相同的时，dp[i][j] = dp[i - 1][j - 1]
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
//当不同的时候，我们需要求三种操作的最小值
//其中dp[i - 1][j - 1]表示的是替换，dp[i - 1][j]表示删除字符，do[i][j - 1]表示的是增加字符
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
}
return dp[word1.length()][word2.length()];
}
