42 | 动态规划实战：如何实现搜索引擎中的拼写纠错功能？

补充一下，中文纠错很多时候是通过拼音进行的，比如 "刘得花"->"liudehua"->"刘德华". 拼音检索方法也有很多，比如可以把热门词汇的拼音字母组织成Trie树，每个热词的结尾汉字的最后一个拼音字母就是叶子，整体性能就是O(n)的，n为query的拼音总长度. 除了拼音外也有根据字形（二维文字版的编辑距离？）甚至语义等做的纠错策略。 传统搜索引擎中的查询词智能提示、纠错、同义词、近义词、同好词、相关搜索、知识图谱等系列功能统称为用户的意图识别模块。

有个疑问： 以下内容涉及“如何编程计算莱文斯坦距离？”一节。 （1）文中对递归树中的状态三元组(i, j, edist)的解释是，“状态包含三个变量 (i, j, edist)，其中，edist表示处理到 a[i] 和 b[j] 时，已经执行的编辑操作的次数。”这里的“处理到a[i]和b[j]时”，其实是在说将要处理但还并未处理a[i]和b[j]。edist并不包括对a[i]和[j]的编辑操作。递归树图片后紧接着的图片中，(i, j, min_edist)的min_edist也并不包括对a[i]和[j]的编辑操作。 （2）而二维状态表图片中每格的值和动态规划的实现代码中minDist[i][j]两者均代表：到处理完a[i]和b[j]之后为止，已经执行的编辑操作的最少次数。根据这个意思，可知状态转移方程中的min_edist(i, j)也是包括对a[i]和[j]的编辑操作的。如果按照（1）中的意思，状态转移方程中的min_edist(i, j)就不应该包括对a[i]和[j]的编辑操作，也不应该判断a[i]和b[j]是否相等，而应该判断的是a[i - 1]和b[j - 1]是否相等；并且动态规划的实现代码中循环终止条件就不应是小于n或m，而应是小于等于n或m。 为什么会有（1）与（2）这样的在文章前后表达上的不一致？

是不是可以这么理解，如果要列出所有可能的情况的通常用回溯算法，而求最佳的情况回溯和dp都可以用，但是有重复子问题的话，可以用dp降低时间复杂度

老师我有个疑问（急），希望老师能够帮忙回答下，这也是大部分留言中没能解决的疑问。 在莱文斯坦距离讲解时，那里的状态方程是怎么直接写出来的？这一点是我最不能理解的，当然在问该问题之前，我已经尽我所能的尝试理解老师的文章，并且把留言也都翻了一遍。老师请看我下面的陈述： 一：按照老师文章的讲解顺序，先分析了如何用回溯方法，然后绘制了递归树，从递归树中又分析出了具有重复的子结构，接着又画出了状态简图（递归树下面的图，不知道怎么表达），从这幅简图中清晰的看出来状态的转移方式，接下来重点来了！！！文章接着就写出来状态转移方程（不理解的地方）！我在留言中发现，老师对这点的解释是说「状态转移方程与递归树无关，递归树仅仅表达了问题具有重复子结构」，如果按照老师的说法，不根据递归树分析出状态转移过程，那该怎么直接写出状态转移方程（要能够合理的推断出来，而不是靠经验，否则还是无法掌握动态规划）？目前来看，我在文章中没有发现具有这样的逻辑推断。我之前的理解是说，我们其实可以在递归树中分析出状态转移方程如何写，然后这样就形成了一个闭环，由回溯->递归树->状态转移方程。希望在这里老师能够给出一个合理的解释？ 二：抛开上面的一些问题，咱们单独看莱问斯坦距离状态转移公式，先假设，按照递归树和递归树下面的图可以知道状态转移的过程（这是一个前提假设）。在留言中的第 4 条「blacknhole」这位同学的留言中，我也有相同的疑问，(i , j, min_edist) 到底表达的是什么状态？（处理完 a[i] b[j] 后的最小距离？ or 刚要处理 a[i] b[j] 时对应的最小距离？）， 接下来按照二种不同的表达来看看状态方程如何推断出来： 1、 如果表达的含义是 「处理完 a[i] b[j] 后的最小距离」 那么其实从回溯算法中可以知道（因为 i j 的前一个状态已经处理完了，比如 min_edist(i-1,j) 就代表了前一个状态。） if (a[i] != b[j]) ​ min_edist(i, j) =1+ min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1)) if (a[i] == b[j] ) ​ min_edist(i, j) = min( min_edist(i-1, j), min_edist(i, j-1), min_edist(i-1,j-1)) 2、如果表达的含义是「刚要处理 a[i] b[j] 时对应的最小距离」 那么我们可以这么想，当前 i,j min_edist 表示还没有处理过 i,j 时对应的状态，因此我们需要考虑之前的状态是怎么传递到这里来的 min_edist(i, j) = min(min_edist(i-1,j)+1, min_edist(i, j-1)+1, min_edist(i-1, j-1) + (a[i-1] == b[j-1]? 0 : 1)) 从上面的两种推断发现，我觉的都是比较合理的，但是没有一种的结果与老师给的状态转移方程是一致的（这一点比较疑惑）？所以对于老师的状态转移方程肯定不是从递归树中直接推导出来的，那么请问老师这个状态转移方程该怎么合理的推断出来（我觉得这个问题不是靠多做题解决的，必须要知道推理逻辑才能彻底掌握动态规划）？ 三：接下来还有一个问题（前提假设是老师的状态方程是正确的，具体逻辑还不能理解） 那么如果根据状态状态方程，来填充状态表的第 0 行 第 0列呢（留言中也有许多这方面的疑问）？按照我的理解，既然状态转移方程我们知道了，那么其实从状态转移方程中就可以直接填充表格了，比如填充第 0 行时，因为从状态转移方程中我们发现有 i - 1,j-1 因此当计算第 0 行时，带有 i-1 项的就可以省略了，因此状态转移方程就剩下 (i, j-1) 项了。然后其实就不用分 a[i] b[j] 是否相等了，但是回头看老师的代码，却不明白为什么还要分 a[i] b[j] 相等不相等。希望老师能够解释一下！ 综上：如果老师觉得我描述的问题不清楚，那么希望老师看看这篇文章的其他问题留言，总结一下大家到底哪里不理解，并且对不理解的地方从新更新下当前文章，具体解释一下，比如老师在留言中说过「不能从递归树中直接推导出状态转移方程，两者没有联系」，那么希望老师在文章的对应地方直接表明这句话，并且在加上额外的说明，比如如何推断出状态转移方程，这样整篇文章才能让更多的人从本质上理解动态规划！ 最后希望老师能够认真给出我上面几个问题的解答，谢谢老师！

老师，您好，您这节内容讲的很清晰透彻，我以前做动态规划问题是直接寻找状态转移方程，基本只能处理一些简单的动态规划问题，没有形成系统的解题思路，听了您这一节后，我觉得将回溯简单思路逐步转化为动规思路让我受益匪浅，但是当我试着将这套思路应用于求解最长递增子序列时却感觉回溯更麻烦，不知能否指点一二

if (a[i] == b[j]) minDist[i][j] = min( minDist[i-1][j]+1,minDist[i][j-1]+1,minDist[i-1][j-1])不明白的是为什么minDist[i-1][j]或者mindist[i][j-1] 要+1呢？

本文举例的 LCS 问题不要求字符连续，通常是指 longest common subsequence 吧？

通过思考题再次发现 找到状态转移方程是多么重要 其他基本都是套路 迭代取极值 到结束

老师状态转移方程，当a[i] = b[j] 的时候，能否把 minDist[i][j] = min(minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]); 改写为 minDist[i][j] = minDist[i-1][j-1]; ？请求老师解答

我怎么感觉，分析完问题后，能不能写出代码的关联点是能不能通过前面的分析写出状态转移方程，跟着老师学的越多，越感觉自己是以前真的是个码农，根本算不上程序员。虽然我才真正做java一年，还是半路出家的，跟着老师学到好多东西，哈哈