算法 – GeekBen

尝试讲清楚编辑距离求解

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

编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将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的长度增长会几何级数的增长。我们需要用程序来求解。

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

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

def lev(a, b):
    if len(a) == 0 or len(b) == 0:
        return max(len(a),len(b))
    if a[0] == b[0]:
        return lev(a[1:],b[1:]) #首字符相等则跳过
    ADD = lev(a,b[1:]) # add b[0]到a的开始, 问题转化为求a,b[1:]的编辑距离，因为头部相同的字符不增加编辑距离
    DEL = lev(a[1:],b) # del a[0]
    REP = lev(a[1:],b[1:]) # set a[0] = b[0], 问题转为求a[1:],b[1:]，原因同计算a的解释
    return 1 + min(ADD,DEL,REP)

def lev(a, b):

if len(a) == 0 or len(b) == 0:

return max(len(a),len(b))

if a[0] == b[0]:

return lev(a[1:],b[1:]) #首字符相等则跳过

ADD = lev(a,b[1:]) # add b[0]到a的开始, 问题转化为求a,b[1:]的编辑距离，因为头部相同的字符不增加编辑距离

DEL = lev(a[1:],b) # del a[0]

REP = lev(a[1:],b[1:]) # set a[0] = b[0], 问题转为求a[1:],b[1:]，原因同计算a的解释

return 1 + min(ADD,DEL,REP)

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

动态规划：括号生成

LeetCode上一个中等难度的题，可以用递归，当然也可以用动态规划（这道题目的状态转移方程有点复杂，定义为中等让我感觉被鄙视了），下面先上动态规划的代码：

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位相同的，已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支，于是求解效率就呈几何级数地提高了。

class Xscoregame:
    def getscore(self, a):
        s = {(0,0):0}
        n = len(a)

        ln = 1<<n
        for i in range(0, ln):
            for j in range(0, 64):
                if s.get((i,j), -1) < 0:
                    continue
                for idx,k in enumerate(a):
                    e = 1 << idx
                    if e & i > 0:
                        continue
                    t = s[(i,j)]
                    t += t ^ k
                    ni = i|e
                    nj = t%64
                    s[(ni, nj)] = max(s.get((ni, nj),-1), t)

        ret = 0
        nn = ln - 1
        for j in range(0, 64):
            ret = max(ret, s.get((nn,j),-1))

        return ret

if __name__ == "__main__":
    print Xscoregame().getscore([1,2,3])
    print Xscoregame().getscore([10,0,0,0])
    print Xscoregame().getscore([1,1,1,1,1,1])
    print Xscoregame().getscore([1,0,1,0,1,0,1,0])
    print Xscoregame().getscore([50,0,1,0,1,0,1,0,1,0,1,0,1,0,1])

class Xscoregame:

def getscore(self, a):

s = {(0,0):0}

n = len(a)

ln = 1<<n

for i in range(0, ln):

for j in range(0, 64):

if s.get((i,j), -1) < 0:

continue

for idx,k in enumerate(a):

e = 1 << idx

if e & i > 0:

continue

t = s[(i,j)]

t += t ^ k

ni = i|e

nj = t%64

s[(ni, nj)] = max(s.get((ni, nj),-1), t)

ret = 0

nn = ln - 1

for j in range(0, 64):

ret = max(ret, s.get((nn,j),-1))

return ret

if __name__ == "__main__":

print Xscoregame().getscore([1,2,3])

print Xscoregame().getscore([10,0,0,0])

print Xscoregame().getscore([1,1,1,1,1,1])

print Xscoregame().getscore([1,0,1,0,1,0,1,0])

print Xscoregame().getscore([50,0,1,0,1,0,1,0,1,0,1,0,1,0,1])

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]

class YetAnotherORProblem2:
    def countSequences(self, n, r):
        ls = {0:1}
        c = 0
        mc = 1
        while mc < r:
            mc <<= 1
        mc -= 1

        for i in range(0, n+1):
            if i == n:
                for k,v in ls.items():
                    c += v
                return c%1000000009
            cs = {0:0}
            for k,v in ls.items():
                mask = mc^k
                # 这里是个重要的优化，大于mask+1的值不可能满足条件
                for j in range(0, mask+1):
                    if k & j == 0:
                        cs[k+j] =  cs.get(k+j, 0) + v
            ls = cs.copy()

class YetAnotherORProblem2:

def countSequences(self, n, r):

ls = {0:1}

c = 0

mc = 1

while mc < r:

mc <<= 1

mc -= 1

for i in range(0, n+1):

if i == n:

for k,v in ls.items():

c += v

return c%1000000009

cs = {0:0}

for k,v in ls.items():

mask = mc^k

# 这里是个重要的优化，大于mask+1的值不可能满足条件

for j in range(0, mask+1):

if k & j == 0:

cs[k+j] = cs.get(k+j, 0) + v

ls = cs.copy()

topcoder: YetAnotherRobotSimulation

又一次暴力求解被羞辱，这个题感觉一定可以for循环代替递归，然而经验值不足（智商感人的委婉说法😢）没能在放弃之前想出来，于是再次拿来主义：

点我展开代码和解析

topcoder: YetAnotherTwoTeamsProblem

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

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

class YetAnotherTwoTeamsProblem:
    def count(self, skill):
        ss = 0
        for i in skill:
            ss += i
        #skill.sort()
        mask = (1 << len(skill)) - 1
        stat = {0:0}
        sm = {0:100000}
        su = {}
        c = 0
        for idx,s in enumerate(skill):
            i = 1<<(idx+1)
            for j in stat.keys():
                n = i|j
                if i == j or stat[j] < 0 or stat.get(n, 1) < 0:
                    continue

                temp = s + stat[j]
                sm[n] = min(sm[j], s)
                h = su.get(temp, {}).get(sm[n], 0)
                stat[n] = temp
                if h != 0:
                    if h == -2:
                        c += 1
                        stat[mask^n] = -1
                    elif h == -1:
                        stat[mask^n] = -1
                    continue

                d = ss - temp
                if temp < d:
                    stat[n] = temp
                elif temp == d:
                    stat[n] = -1
                    stat[mask^n] = -1
                else:
                    if temp - d < sm[n]*2:
                        stat[n] = -2
                        stat[mask^n] = -1
                        c += 1
                    else:
                        stat[n] = -1
                ht = su.get(temp, {})
                if ht == {}:
                    su[temp] = {sm[n]:stat[n]}
                else:
                    ht[sm[n]] = stat[n]

        return c

class YetAnotherTwoTeamsProblem:

def count(self, skill):

ss = 0

for i in skill:

ss += i

#skill.sort()

mask = (1 << len(skill)) - 1

stat = {0:0}

sm = {0:100000}

su = {}

c = 0

for idx,s in enumerate(skill):

i = 1<<(idx+1)

for j in stat.keys():

n = i|j

if i == j or stat[j] < 0 or stat.get(n, 1) < 0:

continue

temp = s + stat[j]

sm[n] = min(sm[j], s)

h = su.get(temp, {}).get(sm[n], 0)

stat[n] = temp

if h != 0:

if h == -2:

c += 1

stat[mask^n] = -1

elif h == -1:

stat[mask^n] = -1

continue

d = ss - temp

if temp < d:

stat[n] = temp

elif temp == d:

stat[n] = -1

stat[mask^n] = -1

else:

if temp - d < sm[n]*2:

stat[n] = -2

stat[mask^n] = -1

c += 1

else:

stat[n] = -1

ht = su.get(temp, {})

if ht == {}:

su[temp] = {sm[n]:stat[n]}

else:

ht[sm[n]] = stat[n]

return c

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

topcoder: ZigZag

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

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

上代码：

class ZigZag:
    def longestZigZag(self, seq):
        count = 1
        d = 0
        p = seq[0]
        for i in seq[1:]:
            if p == i:
                continue
            elif p < i:
                if d == 1:
                    p = i
                    continue
                else:
                    count += 1
                d = 1
            else:
                if d == -1:
                    p = i
                    continue
                else:
                    count += 1
                d = -1
            p = i

        return count

class ZigZag:

def longestZigZag(self, seq):

count = 1

d = 0

p = seq[0]

for i in seq[1:]:

if p == i:

continue

elif p < i:

if d == 1:

p = i

continue

else:

count += 1

d = 1

else:

if d == -1:

p = i

continue

else:

count += 1

d = -1

p = i

return count

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

topcoder practice: ZooExchangeProgram

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

题面：

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

代码及详解：

class ZooExchangeProgram:
    def getNumber(self, label, lower, upper):
        l = list(label)
        # 这个r就是我们最后要通过各种现有label组的合并达到的目标集合
        r = range(lower, upper+1)

        # 简单的将无解的情况排除
        for i in r:
            if i not in l:
                return -1

        # 按照给定的目标集合，将所有在包含于目标集合的label组都整理出来
        groups = []
        start = 0
        for i,x in enumerate(l):
            if x not in r:
                if start < i:
                    groups.append(set(l[start:i]))
                start = i + 1
            elif i == len(l) - 1:
                groups.append(set(l[start:i+1]))

        # 去除重复的组，因为我们最终求解的是达成目标集合所需要最小的组数量，答案不用给出包含具体某个组的信息，所以去重不影响结果，只会加速求解；这一段代码体现了python的简洁，一个in关键字就可以代替C语言的compare函数，虽然背后的效率肯定比C低，但是这对让程序员关注算法本身提供了极大便利。当然还有其它更加高效的list of lists去重方法，比如使用库itertools，但是本题的限制了label的数量为50个之内，所以最多有50个组，双重循环一次也还能接受。
        ng = []
        for i in groups:
            if i not in ng:
                ng.append(i)

        # tricky part: 这里开始才是本题的精髓，使用的是动态规划；状态定义为某个组所覆盖的元素集合，或者多个组的并集所覆盖的元素集合，最终状态就是目标集合，而每个组，或者每种多组的并集所构成的所有状态都是中间状态；而且，达成同一种状态可能有多种组合形式；暴力求解方法就是搜索计算所有这些组构成的全部组合形式，将其中构成最终状态的组合记录下来，然后从中找到由最少组构成的组合；这种方法所需计算量非常大，因为其搜索过程中放弃了很多中间结果，为了搜索到一组可能解，过程中走过的弯路，在下一组求解中可能仍然要重新走一遍，这是极大的浪费；动态规划思想记录下搜索过程中的任何一次尝试结果。本题中，我们要纪录的就是每次搜索到某个中间状态时所需要的组合数，下次再组合出这种状态时，比较以前记录下来的值，如果本次组合数更小则更新记录；这样，只需遍历一次所有组合，就能得到所有可能的中间状态的最小组合数，届时只需要从中选择那个最终状态对应的组合数即可。
        count = [0] * 50
        state = {0:0}
        mode = []
        mask = 0
        ret = 0

        # 这里是为了优化程序的执行时间，需要将那些必须选入组合的组排除出我们搜索的范围，反正无论如何它们都得入选，我们干嘛还要去考虑它们呢，博主一开始就是没有排除它们，在提交后被判失败，自己测试发现其中一个case居然耗费了12s之多。哪些是必选的呢，就是那些包含了别人都没有的元素的组，到这里我们所说的组都是包含于目标集合的，所以有独一无二的元素的组必须入选。
        # 先计算所有目标集合中的元素哪些是只存在于一个组中的
        for i in ng:
            for j in i:
                count[j] += 1
        # 对独一无二的元素，我们单独处理，把它们排除在搜索范围（搜索范围的组构成mode）内，然后将它们所在的组的并集mask记录下来；其它的组计算出它们的状态值作为key保存在字典state里面，对应的value记为1，即这种状态显然只需要对应的单个组自己就能构成。
        # 之所以用字典，而不用list，因为list的索引必须是连续的，即使中间很多item都没有用到，也要为他们分配内存，这样的话会浪费大量的内存，比如我们这题当中的label最大可以到50，也就是说从1到50，这50个label会有1<<50种可能的状态组合，那我们需要一个1<<50，即1*2^50，即使用最小的byte型数组（python好像不能指定类型），那也是1024TB的内存，博主开始也没有意识到这个问题，直接用了list，在测试过程中python报memory error才恍然发现了这么个大bug。而python提供了字典这么好的一个数据结构，使用字典可以做到用多少给多少，大大大的减少了内存浪费。
        for i in ng:
            temp = 0
            only = False
            for j in i:
                if count[j] == 1:
                    only = True
                temp += 1<<(j-1)
            if not only:
                mode.append(temp)
                state[temp] = 1
            else:
                mask |= temp
                ret += 1

        if mask == (1<<upper)-(1<<(lower-1)):
            return ret

        best = 50 # 不会比50个组的组合更差的情况了
        for m in mode:
            for i in state.keys():
                # 新的状态可由老状态和m组成，但未必比历史记录更优
                state[i|m] = min(state.get(i|m,50), state.get(i,50)+1)
                if mask|i|m  == (1<<upper)-(1<<(lower-1)):
                   best = min(best, ret+state[i|m])

        return best

class ZooExchangeProgram:

def getNumber(self, label, lower, upper):

l = list(label)

# 这个r就是我们最后要通过各种现有label组的合并达到的目标集合

r = range(lower, upper+1)

# 简单的将无解的情况排除

for i in r:

if i not in l:

return -1

# 按照给定的目标集合，将所有在包含于目标集合的label组都整理出来

groups = []

start = 0

for i,x in enumerate(l):

if x not in r:

if start < i:

groups.append(set(l[start:i]))

start = i + 1

elif i == len(l) - 1:

groups.append(set(l[start:i+1]))

# 去除重复的组，因为我们最终求解的是达成目标集合所需要最小的组数量，答案不用给出包含具体某个组的信息，所以去重不影响结果，只会加速求解；这一段代码体现了python的简洁，一个in关键字就可以代替C语言的compare函数，虽然背后的效率肯定比C低，但是这对让程序员关注算法本身提供了极大便利。当然还有其它更加高效的list of lists去重方法，比如使用库itertools，但是本题的限制了label的数量为50个之内，所以最多有50个组，双重循环一次也还能接受。

ng = []

for i in groups:

if i not in ng:

ng.append(i)

# tricky part: 这里开始才是本题的精髓，使用的是动态规划；状态定义为某个组所覆盖的元素集合，或者多个组的并集所覆盖的元素集合，最终状态就是目标集合，而每个组，或者每种多组的并集所构成的所有状态都是中间状态；而且，达成同一种状态可能有多种组合形式；暴力求解方法就是搜索计算所有这些组构成的全部组合形式，将其中构成最终状态的组合记录下来，然后从中找到由最少组构成的组合；这种方法所需计算量非常大，因为其搜索过程中放弃了很多中间结果，为了搜索到一组可能解，过程中走过的弯路，在下一组求解中可能仍然要重新走一遍，这是极大的浪费；动态规划思想记录下搜索过程中的任何一次尝试结果。本题中，我们要纪录的就是每次搜索到某个中间状态时所需要的组合数，下次再组合出这种状态时，比较以前记录下来的值，如果本次组合数更小则更新记录；这样，只需遍历一次所有组合，就能得到所有可能的中间状态的最小组合数，届时只需要从中选择那个最终状态对应的组合数即可。

count = [0] * 50

state = {0:0}

mode = []

mask = 0

ret = 0

# 这里是为了优化程序的执行时间，需要将那些必须选入组合的组排除出我们搜索的范围，反正无论如何它们都得入选，我们干嘛还要去考虑它们呢，博主一开始就是没有排除它们，在提交后被判失败，自己测试发现其中一个case居然耗费了12s之多。哪些是必选的呢，就是那些包含了别人都没有的元素的组，到这里我们所说的组都是包含于目标集合的，所以有独一无二的元素的组必须入选。

# 先计算所有目标集合中的元素哪些是只存在于一个组中的

for i in ng:

for j in i:

count[j] += 1

# 对独一无二的元素，我们单独处理，把它们排除在搜索范围（搜索范围的组构成mode）内，然后将它们所在的组的并集mask记录下来；其它的组计算出它们的状态值作为key保存在字典state里面，对应的value记为1，即这种状态显然只需要对应的单个组自己就能构成。

# 之所以用字典，而不用list，因为list的索引必须是连续的，即使中间很多item都没有用到，也要为他们分配内存，这样的话会浪费大量的内存，比如我们这题当中的label最大可以到50，也就是说从1到50，这50个label会有1<<50种可能的状态组合，那我们需要一个1<<50，即1*2^50，即使用最小的byte型数组（python好像不能指定类型），那也是1024TB的内存，博主开始也没有意识到这个问题，直接用了list，在测试过程中python报memory error才恍然发现了这么个大bug。而python提供了字典这么好的一个数据结构，使用字典可以做到用多少给多少，大大大的减少了内存浪费。

for i in ng:

temp = 0

only = False

for j in i:

if count[j] == 1:

only = True

temp += 1<<(j-1)

if not only:

mode.append(temp)

state[temp] = 1

else:

mask |= temp

ret += 1

if mask == (1<<upper)-(1<<(lower-1)):

return ret

best = 50 # 不会比50个组的组合更差的情况了

for m in mode:

for i in state.keys():

# 新的状态可由老状态和m组成，但未必比历史记录更优

state[i|m] = min(state.get(i|m,50), state.get(i,50)+1)

if mask|i|m == (1<<upper)-(1<<(lower-1)):

best = min(best, ret+state[i|m])

return best