转自面向大象编程 本期例题:LeetCode 72. Edit Distance 编辑距离(Hard)
今天我们要讨论一道经典的二维动态规划问题:编辑距离(Edit Distance)。 你可能在各种地方都听说过「编辑距离」。编辑距离又叫莱文斯坦距离(Levenshtein distance),用于评估两个字符串的差异程度,在拼写检查、文本对比(diff)等场景中都有应用。编辑距离问题的实际意义使得它非常受面试官青睐。 编辑距离问题是 LeetCode Hard 题目,很多同学做这道题的时候会觉得很难,总是找不到思路。这道题的难点主要有两个:
今天的文章会以编辑距离问题为例,讨论如何攻克动态规划问题的这两个难点。我们先讲讲如何从复杂的问题中拆解出动态规划的思路,再讲讲如何在动态规划题目之间进行联想。 编辑距离的拆解思路假设你已经知道了编辑距离这道题是用动态规划来做,那怎么能进一步得出具体的思路呢? 动态规划题目的解题步骤我们都知道,要先定义子问题,再写出子问题的递推关系。道理我们都懂,但是对于具体的题目,如何定义子问题和子问题的递推关系还是很需要技巧的。 如果直接从整体看编辑距离,其实很难下手。究竟怎样组合插入、删除、替换操作,才能得到最少的编辑次数呢?这些操作之间又满足怎样的性质呢? 在做动态规划问题的时候,如果你觉得从全局考虑很困难,就试试先不考虑全局,从局部入手。我们可以只考虑其中的「一步」,至于剩下的步骤,就交给其他子问题完成就行。对于编辑距离来说,这「一步」就是指「单次的编辑操作」。 我们以 'horse' 和 'ros' 为例。我们考虑这「一步」做的是插入、删除还是替换操作。
为什么要关注「一步」呢?因为动态规划最关键的地方在于寻找「子问题的递推关系」,或者叫「状态转移方程」。所谓「递推关系」,就是一个子问题经过怎样的「一步」操作可以转换为另一个子问题。 例如,之前讲过的打家劫舍问题,计算子问题 的时候,我们可以有两种选择: 由 计算而来,或者 由 计算而来。也就是说,子问题 可以转换为 或 。 这有点类似递归的思路。我只需要把当前这一步计算做好,然后相信递归函数能帮我做好剩下的计算。动态规划其实很像递归,只不过动态规划一般是自底向上计算,保存每个子问题。 对于编辑距离问题,我们的「一步」有三种「选择」。选择插入、删除或者替换操作,我们可以将当前子问题转换为不同的子问题: 这样,编辑距离的子问题如何定义其实就相当清楚了。不同的子问题其实就是 这样,我们就有了动态规划解法的基本思路,接下来,我们继续套用动态规划的「解题四步骤」,来给出完整的题解吧。 套用解题四步骤老规矩,我们使用动态规划的解题四步骤来写出题解代码。 步骤一:定义子问题上文我们已经讨论了两个字符串的动态规划问题的子问题套路。和最长公共子序列问题一样,我们可以定义子问题 为「 步骤二:写出子问题的递推关系子问题的递推关系就和三种编辑操作相对应。对于
对于这三种方案,我们需要找出其中操作最少的方案。用公式写出来的话,就是: 需要注意的是,上面的「替换」方案,如果 第一种情况:如果 第二种情况:如果 这样,我们得到最终的子问题递推关系为: 另外,别忘了递推关系的 base case。
步骤三:确定 DP 数组的计算顺序对于二维动态规划问题,我们需要定义二维的 DP 数组,其中 设 为了确定 DP 数组的计算顺序,我们需要知道子问题的依赖方向。观察子问题的递推关系, 依赖于 、 和 ,我们在 DP 数组中画出依赖方向的箭头: 我们发现,编辑距离问题的子问题依赖方向和最长公共子序列问题一模一样!这是因为,在两道题目中, 都依赖于 、 和 。虽然具体的递推关系不一样,但是只要是这样的依赖关系,DP 数组的计算顺序就是一样的。 那么,编辑距离问题,DP 数组的计算顺序同样是从左到右、从上到下。我们应该以这样的顺序遍历 DP 数组:
最终我们得到的题解代码为: public int minDistance(String s, String t) { 这个算法的时间、空间复杂度均为 ,其中 、 分别表示 步骤四:空间优化(可选)编辑距离问题本身属于较难的题目,所以我们写出基本的解法就可以,一般面试中不会追问空间优化的方法。 实际上,编辑距离、最长公共子序列这类问题有一种共同的空间优化方法。后面我会专门写一篇文章,给大家讲述动态规划的各种空间优化套路。 从 LCS 问题联想出思路以上我们讲解了在「知道这道题是动态规划」的情况下该怎么拆解子问题。那么你可能要问了,在刚拿到这道题的时候,怎么才能想到它是一道动态规划题目呢? 答案很简单,从做过的题目进行联想。如果你觉得这道题和某个动态规划题目很像,那它多半可以用动态规划来做。 这道编辑距离问题,其实和我们讲过的最长公共子序列(LCS)问题非常相似。这两个题目都是涉及到两个字符串比较的「双串」题目。很容易联想到。 如果你对最长公共子序列(LCS)题目不太了解,可以回顾之前的文章: LeetCode 例题精讲 | 15 最长公共子序列:二维动态规划的解法 我用 LCS 作为二维动态规划的例题,就是因为它的方法非常经典,很多其他题目中都有它的影子。 LCS 问题中其实蕴含了两个解题的小套路:
LCS 问题是关于求公共的子序列。编辑距离问题乍一看没有什么子序列,但联想起来,其实非常相似。 仔细看编辑距离问题的「插入」、「删除」、「替换」三个操作。其中「插入」和「删除」是相反的操作,从 那么,我们其实可以把所有的操作归类调整,分为三个阶段:
例如,下图中是 'intention' 转换为 'execution' 的实际例子: 这样就可以看出编辑距离问题也和「子序列」类问题非常相似。那么我们从这一点想到用动态规划的解法,也就很正常了。 在想到可以用动态规划解题之后,我们再根据具体的题目描述拆解子问题,前面的部分我们已经讲解了具体的操作了。 总结本文用编辑距离问题展示了从实际问题中分析动态规划思路的技巧。很多动态规划的难题都是需要一定的拆解技巧。例如比较著名的两道:
(这两道题目都比较难,初学者不要轻易尝试) 同时,本文还展示了编辑距离问题与 LCS 的相似之处。两道题因为子问题的依赖关系是相同的,所以 DP 数组的计算顺序也完全一致。其实,很多动态规划题目都是可以「触类旁通」的。在刷题的时候,把做过的题目理解、吃透,能够让你在做新的题目的时候有更多的思路。 |
|
来自: 520jefferson > 《数据结构与算法》