编辑距离问题

编辑距离问题

题目描述：

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
* 插入一个字符
* 删除一个字符
* 替换一个字符
示例：
    输入: word1 = "horse", word2 = "ros"
    输出: 3
    解释: 
        horse -> rorse (将 'h' 替换为 'r')
        rorse -> rose (删除 'r')
        rose -> ros (删除 'e')

解题

设置`dp[][]`，元素`dp[i][j]`表示单词`word1[0...i]`到单词`word2[0...j]`的编辑距离。<br />    使用动态规划的关键在于：<br />    既然元素`dp[i][j]`是最优子结构，那么`word1[i]`要么发生了替换，要么插入，删除，或者匹配。

• 如果dp[i][j]的最优解是通过删除word1[i]来达到的，那么dp[i - 1][j]作为最优子结构，它的值一定是dp[i][j] - 1。可以使用反证法来证明。

• 其他的情况（插入，匹配，替换）类似。

  状态转移为： ``` // 有四种情况 dp[i][j] = min { dp[i - 1][j - 1], // 匹配 dp[i - 1][j - 1] + 1, // 替换 dp[i][j - 1] + 1, // 在word1[i]后方插入 dp[i - 1][j] + 1, // 删除 };

```