大家好，我是小风哥。这是动态规划话题的第三部分。这篇文章的题目很经典，几乎是面试必备，就是editdistance的问题，editdistance；给定两个字符串word1和word2，返回将word1转换为word2所需的值最少步骤，在每个步骤中你可以对字符串word1执行以下操作：添加一个字符删除一个字符替换一个字符如果word1是“horse”并且word2是“ros”，那么你的程序需要返回3，也就是说word1到word2至少需要三步：将word1中的第一个字符h替换为字符r：horse->rorse，此时word1变成rorse，word1和word2的前两个字符相等。删除第三个字符r：rorse->rose，此时word1变为rose，word1和word2的前三个字符相等删除word1中的最后一个字符：rose->ros，此时word1和word2相等。想想如何使用动态规划来解决这个问题。选择和子问题和前面的问题一样，首先要搞清楚子问题是什么，子问题对原问题的依赖是什么。找出子问题的关键在于每一步的选择。如果word1和word2的首字符相等，假设word1是hor，word2是hr，那么我们可以安全的排除两个字符串的首字符，即EditDistance("hor","hr")一定等于EditDistance("or","r"):此时我们得到一个子问题EditDistance("or","r")，与原问题EditDistance("hor","hr")的值相等到子问题。真正有意思的是，如果word1和word2的首字符不相等，假设word1是“hor”，word2是“ro”，那么根据题的规则，对第一个字符的操作有3种word1:1.在word1的第一个字符前添加（Insert）一个字符r。这时候word1就变成了rhor。由于word1的第一个字符等于word2的第一个字符，所以可以放心地忽略它，所以我们得到了子问题EditDistance("hor","o")，因为有一个新的操作，所以：EditDistance("hor","ro")=EditDistance("hor","o")+12，删除word1的第一个字符（Delete），word1变成"or"，我们得到一个新的子问题EditDistance("or","ro"),因为进行了删除操作，所以：EditDistance("hor","ro")=EditDistance("or","ro")+13、将word1的第一个字符替换（Replace）为r，此时word1变成了“ror”，由于第一个字符等于word2的第一个字符，所以可以放心忽略，我们得到一个新的子问题EditDistance(“or”,“o”),因为进行了删除操作，所以：EditDistance("hor","ro")=EditDistance("or","o")+1根据题目的要求，我们需要得到最小编辑距离，所以:EditDistance("hor","ro")=min(EditDistance("hor","o"),EditDistance("or","ro"),EditDistance("or","o"))+1即：可以看到如果word1和word2的第一个字符不相等那么我们会得到三个子问题，取这三个子问题中的最小值在原解的基础上加1问题。现在我们已经找到了子问题和原问题之间的依赖关系。实际上，根据上面的讨论，我们可以进一步展开得到一个完整的状态空间树。您可以从这棵树中看到最小编辑距离为2。现在你应该清楚地知道我们是如何一步步把问题分解成更小的子问题，然后用子问题的解来得到原问题的解了。自上而下的递归代码上图中的每个框都是一个子问题。决定一个子问题的因素是word1和word2当前处理的位置。假设word1已经处理到第i个位置，word2已经处理到第一个位置。j个位置，所以我们可以定义问题：intEditDistance(inti,intj);该函数表示从i到word1末尾的字符串与从j到word2末尾的字符串之间的编辑距离。因此，如果我们调用这个函数，我们应该这样使用：EditDistance(0,0);有了这个定义和上面的分析，就可以很容易的写出这样的递归代码：))返回0；如果(i==word1.length())返回word2。长度（）-j;如果(j==word2.length())返回word1.length()-i;如果(word1[i]==word2[j])返回EditDistance(i+1,j+1);else{returnmin(EditDistance(i+1,j+1),min(EditDistance(i,j+1),EditDistance(i+1,j)))+1;}}我们把word1和word2声明为全局变量，所以可以很清楚的看到EditDistance函数的值的决定因素只有i和j这两个参数，i的值为[0,word1.length()]，而j的值为[0,word2.length()]，也就是说子问题的个数只有(word1.length()+1)*(word2.length()+1)。上面的递归代码有很多重复计算的问题，所以可以通过加缓存的方式来优化。这个改变留给大家。接下来我们着手将自上而下的递归代码更改为自下而上的动态编程代码。自下而上的动态规划代码由于子问题的个数只有(word1.length()+1)*(word2.length()+1)，可以定义一个同样大小的二维数组dp:vector
