尝试讲清楚编辑距离求解

这篇文章是尝试给像作者一样的算法爱好者(业余的委婉说法)解释一下编辑距离求解方法的思考过程,其实也是为了强迫自己真正的吃透编辑距离求解的方法论,以期能达到举一反三的效果。根据以上受众定位,我首先还是引入一段对编辑距离的解释,然后再从递归到递推(动态规划)讲讲对这个问题求解本身的正向思考过程,而不是拿到一个解法来说明它的正确性。

编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将horse转化为ros,可以是如下步骤:
1)删除h变成orse; 2)删除o变成rse; 3)增加o变成rose; 4)删除e变成ros
也可以是如下步骤:
1)改h为r变成rorse; 2)删r变成rose; 3)删e变成ros
显然第二种策略要优于第一种,但是这种演变策略的排列组合随着源串a和目的串b的长度增长会几何级数的增长。我们需要用程序来求解。

这是一个典型的考动态规划的编程题,很多文章都会给出一个递推公式,但是这个递推公式为何正确,得到这个公式的思考过程是啥,为什么这么思考?回答了这几个问题才算理解了编辑距离的精髓,而且才能有举一反三的可能性。看了很多解释的文章,感觉都是从结果来理解和解释递推过程反证过程的有效性,隔靴搔痒,没有讲到这个公式是怎么得来的,怎么一下子就能得出这么精妙的计算方法,感觉就像现在解释机器学习模型的原理那样,训练出来一个有效的神经网络结构,然后再试图解释每一层是在干嘛,然而并不是一开始设计的时候就知道会是这样。但编辑距离这个算法是完全由人想出来的,必然是有设计者的心路历程可循。下面讲下我对这个问题的理解思路。

最容易想到的方法是递归,递归函数以目标字符串和源字符串为输入参数,代码如下:

Continue reading “尝试讲清楚编辑距离求解”

topcoder: Xscoregame

这一题用递归很简单,直接深度优先搜索所有排序,取最大值即可,但是完全没有DP的思想而且求解时间不可接受;但是如果要DP,如何减少状态数?要知道本题的输入数列排序是影响最终结果的。

下面的解法是DP的,这个DP的妙处在于仍然用输入数列A的子数列组合As作为状态,但是这个状态下面仍然分一些子状态,不过不是用这个子数组的所有排序作为子状态而是用一种hash的方式,即将该子数组的可能结果(子数组每一种排序按题目算法所求得的状态值R=x+x^As[i])对64(2的6次方)求余所得作为子状态的index。

为什么可以这么做?因为题目中数组A最大的数为50(6bit,可覆盖),所以在一个状态转移到下一状态时,即某个子数组新加入一个元素的时候,其实只需要考虑状态值R的低6位不同的情况即可,因为只有低6位有后效性,只有低6位相同的所有排序只需取最大状态值(这里不用求具体排序,主要求最大值),其他都不用考虑了,而不同的低6位值可能带来不同的有效子状态。说白了,就是当前低6位不一样的,现在不能判定以后谁优谁劣,而当前低6位相同的,已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支,于是求解效率就呈几何级数地提高了。

 

topcoder: YetAnotherORProblem2

这题显示只有18%的AC率,题目本身不难,估计都是败在执行时间上了;我的解法如下,典型的DP思维,子问题是:如果已知长度为n-1的情况下,和或操作相等的数列,求长度为n的情况;状态index为每个满足条件的数列的和Sn-1(因为和或相等,也是该数列的或),状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

 

topcoder: YetAnotherTwoTeamsProblem

这是一道标记为hard的题,确实比较hard

开始用了一个比较简单暴力的方法,其实也是DP思路,但是状态取的比较偷懒,直接用了所有的可能组合作为状态,虽然在求解过程中可以利用到已经搜索过的状态,但是整个搜索空间还是太大了,导致虽然结果正确,但是严重超时了:

又做了一次伸手党,看了解答后醒悟了,其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

topcoder: ZigZag

再来水一道简单题:题目地址

想法很自然,记录下当前的方向,一旦出现方向不一致的就把总数加一,同时方向改变,否则continue,然而其实已经包含了动态规划思想

上代码:

看了下别人提交的,思路一样,只不过有人上来先把整个序列的变化趋势算一遍,即遍历seq,然后算出seq[i]-seq[i-1]的值记录下来记为V[i],其实要的就是一个正负号,然后再次遍历还是记录当前的方向,乘以当前遍历到的那个趋势V[i],乘积发生变化时就在结果上加一并改变当前方向值。

topcoder practice: ZooExchangeProgram

为了兴趣,也为了保持coding的能力,重新开始写一些算法题;为了对算法了解的更透彻,也为了锻炼表达能力,干脆在博客里面对解题代码进行详解,代码是自己写的,但也不排除参考了别人的解法,消化吸收了就是自己的,不是吗?

题面:

太长了,就不贴了,链接在此

代码及详解: