动态规划问题之编辑距离

前言：编辑距离此题为LeetCode的第72号题，本质上可以采用动态规划DP的方法求解，但是在求解的时候理解出现了问题，导致懵逼了一段时间，还好终于想通了，现将自己的理解思路整理如下，希望可以帮到大家。

问题描述：
    给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

    你可以对一个单词进行如下三种操作：

    ---插入一个字符 
    ---删除一个字符 
    ---替换一个字符

 注意：首先我们需要明确一点，那就是我们将word1转换成word2，因此我们必须对word1进行上述3种操作，而不是对word2，因此我之前看到不少文章对于此点没有说明白，对于准确理解此题造成了一点阻碍。

关于动态规划求解的步骤，这篇文章感觉说的很好：https://zhuanlan.zhihu.com/p/91582909

DP问题的求解一般遵循3个步骤：定义数组元素的含义、找出初始值和找出数组元素之间的关系

• 定义数组元素的含义

这一步我们定义起来比较简单，dp[i][j] 代表着word1的前i个字符转换成word2的前j个字符所需要的最少操作步数，虽然将它定义出来比较简单，但是我们必须要理解对数组的含义，我之前就是因为理解有偏差导致迟迟对此问题理解不了，需要注意的是：定义中的i和j代表的是前i个字符和前j个字符，也就是说我只要将word1的前i个字符转换成word2的前j个字符就OK了，后面的字符我不管，至于怎么转换我也不管，只要转换过去就行，理解这一点很重要。 

• 找出数组元素之间的关系

DP规划问题的思路就是通过前面已有的结果去推出当前的结果，而不用从头开始去推，对于此问题而言，dp[i][j]代表的是 word1的前i个字符转换成word2的前j个字符所需要的最少操作步数，那我们就需要用到前面已经转换的不同长度的字符串的最少转换步数。由于插入、替换、删除3种操作每次都是影响word1的一个字符，所以求dp[i][j]顶多会用到dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1][j]的值，也就是说在二维网格图中距离dp[i][j]距离为1并且在dp[i][j]左方和上方的数据。

首先，我们需要分情况讨论：

情况1：word1的第i个字符和word2的第j个字符相同

既然相同的话，也就是说我们不用对word1的第i个字符进行任何操作就能够变成word2的第j个字符（因为两者相等），所以我们将前i个字符转换为前j个字符的步数和前i-1转换成前j-1的步数相等，那么我们可以得到关系式：    dp[i][j] = dp[i-1][j-1]

情况2：word1的第i个字符和word2的第j个字符不同

既然不同，那么我们就需要在前面不同长度字符转换的基础上对word1进行进一步的操作，注意我们是对word1进行的操作，切记！那么我们进行什么样的操作呢？

操作1：删除

我们可以想一下，什么情况下仅仅需要对word1删除一个元素就可以完成前i个字符转换成word2的前j个字符呢？删除一个字符，意味着word1前i-1个字符已经转换为word2的前j个字符了，我现在要再转换word1的第i个字符，那么多做一步操作直接将其删掉就可以了，那么我们可以得到关系式：     dp[i][j] = dp[i-1][j] + 1

 

                                         

操作2：插入

对word1插入一个字符才能完成转换，插入的字符必然和word2的第j个字符相等，也就是说我们之前已经将word1的前i个字符转换为word2的前j-1个字符了，那么如何才能完成转换成word2的前j个字符呢？直接对word1进行近一步操作，再加一个与word2的第j个字符相等的字符就可以了，那么我们就可以到得到关系式：    dp[i][j] = dp[i][j-1] + 1

                                           

操作3：替换

需要替换是需要将word1的第i个字符替换成word2的第j个字符，也就是说之前我们已经将word1的前i-1个字符转换成word2的前j-1个字符，只需要将word1的第i个字符替换成word2的第j个字符，那么我们可以得到关系式：  dp[i][j] = dp[i-1][j-1] + 1

                                               

至此我们讨论了3种可以利用之前的结果得到dp[i][j]的方式，并且利用的是前面已经解决的不同的结果，我们需要的是最少的步数，因此总的表达式为：

dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

• 找出初始值

通过前面的数组之间的关系式，我们可以知道表达式左侧i和j的值最小从1开始，不能为0，因为如果为0的话，表达式右侧数组坐标就会出现负值了。因此我们需要得到dp[0][j],和dp[i][0]

对于dp[0][j]来说，意味着将长度为0的字符串转换为长度为j的字符串，因此执行的操作就是不断的插入值，总共需要j步

因此    dp[0][j] = j

对于dp[i][0]来说，意味着将长度为i的字符串转换为长度为0的字符串，因此执行的操作就是不断的删除值，总共需要i步

因此    dp[i][0] = i