Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
听人家说，这是 双序列DP问题. 确实，对我来说，这个题的解法好难理解，即使之前做出了几个dp问题．我怎么可能说自己笨呢!
四个优秀的解释：
http://www.stanford.edu/class/cs124/lec/med.pdf
http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html
http://www.jianshu.com/p/39115986db5a
http://www.dreamxu.com/books/dsa/dp/edit-distance.html
一个分治、dp、贪心的优秀小 book：
http://www.dreamxu.com/books/dsa/dc/subset.html
看了人家很多解释，还是自己想出个例子，自己再顺一遍才能较好的理解．Come on!
假设有 3 种操作：
插入，删除 和 修改．假设它们的 cost 均为 1;
注意有的题目可能它们的 cost 不相同, 比如:
- The costs of both insertion(插入) and deletion(删除) are same value, that is 1;
- The cost of substitution(替换) is 2．
咱自己的例子：
说例子前需说明什么是 dp[i, j].
dp[i, j] 称为 s1[0..i] 串到 s2[0..j] 的最小距离． 表示 字符串 s1[0..i] 转变成 s2[0..j] 的最小代价．在我们的题中，也可理解为最小步骤(因为无论啥操作，cost都是１).
这句话当初对我来说并不好理解．为了更容易的让大家理解，举个例子：
本解释将跟随题目要求，cost 均为１.
符号 ＂＊＂ 代表空字符串．
s1 = "a"
s2 = "b"
现在要把 s1 变成 s2，问：最少的步骤是多少？ 显然，这种情况下，凭直觉，肯定是1步，既， 1步 substitution.
此时：
这是要对 s1 做 substitution 操作, 将 a 替换成 b:
dp[i, j] = dp[i-1, j-1] + 1 = dp[0, 0] + 1 = 0 + 1 = 1;
若 s1 的第一个字符 a 和 s2 的第一个字符一样的话： dp[1, 1] = dp[0, 0] = 0, 就不需要替换操作了．
* a
^
i=1
* b
^
j=1
dp[i = 1, j = 1] 可以写成 dp[i = 0, j = 0] + 1． 就是 s1[0..1] 的串变成 s2[0..1] 的串可表示成 s1的空串变成s2的空串所需次数 + 1.
空串变空串？那还用变？精神病的做法是 ＊ -> a －＞＊,这个cost = 2, 而dp里存的是最小次数或叫做最下距离，那么显然 dp[i = 0, j = 0] = 0 (空串变空串？两个空串有什么好变化的，对吧)
但真的只有这一种办法吗？不是的．看下面：
这是 s1由空变为b 步骤数已知的情况下, 再删除a:
dp[i, j] = dp[i-1][j] + 1 = 1 + 1 = 2
* a
^
i-1=0
* b
^
j=1
还有一个情况：
这是 s1="a" ,删除a变成空的步骤数已知的情况下，再在最后面插入一个b:
dp[i, j] = dp[i][j-1] + 1 = dp[1][0] + 1 = 1 + 1 = 2
* a
^
i=１
* b
^
j-1=0
dp[i, j]只与其左上，左，上，有关．分别为 dp[i-1,j-1], dp[i,j-1] and dp[i-1,j].
总结起来步骤是这样的：
- m = s1 的长度， n = s2 的长度;
- 初始化边界：
dp[0][j] = j, dp[i][0] = i，其中i = [0,..,m], j = [0,..,n]. 就是空串变某个串, 或某个串变空串的步骤数，肯定是那个串的长度了; - 若
s1[i - 1] = s2[j - 1], 则dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));这表示若dp[i - 1][j - 1], dp[i - 1][j]+1, dp[i][j - 1]+1已知, 则由这３种 case所表达的状态 到dp[i][i]的状态．我们取上述三种状态的最小值赋值给dp[i][j]. 其中dp[i - 1][j - 1]不用加１是因为s1和s2最后一个字符是一样的，当然不用再加１，否则＋１(就是修改s1最后字符为s2最后字符，其实说最后字符是不妥当的，我们直接认为当前正在处理s1,s2最后面的那个字符，这么想能使问题简单一些.) - 若
s1[i - 1] != s2[j - 1], 则dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));注意，除了dp[i - 1][j - 1] + 1有变化外，其他没变． - 空间复杂度问题：我们可以维护一个(m+1) * (n+1) 的 dp 矩阵，另一种更好的办法是只维护一个 m 或 n 大小的数组.
人家想法，咱的代码:
方法一:
(O(m*n)) time, (O(m*n)) extra space.
int minDistance(string word1, string word2) {
int m = word1.length(), n = word2.length();
// dp: a (m+1) * (n+1) matrix
vector < vector<int> > dp(m + 1, vector<int>(n + 1, 0));
// fill values in boundary
for (int i = 0; i <= m; i++)
dp[i][0] = i;
for (int j = 0; j <= n; j++)
dp[0][j] = j;
// dp state transfer formula
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (word1[i - 1] == word2[j - 1])
dp[i][j] = min(dp[i - 1][j - 1],
min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
else
dp[i][j] = min(dp[i - 1][j - 1] + 1,
min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
return dp[m][n];
}
方法二:
(O(m*n)) time, (O(m)) extra space.
墨迹了挺长时间，没写出来．
看人家的吧．https://leetcode.com/problems/edit-distance/discuss/
写本文的时候发现，文字描述起来好费劲，啰里啰嗦，自己写作水平根本不行啊．