GeekBen

这一题用递归很简单，直接深度优先搜索所有排序，取最大值即可，但是完全没有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])

这题显示只有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()

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

点我展开代码和解析

这是一道标记为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

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

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

想法很自然，记录下当前的方向，一旦出现方向不一致的就把总数加一，同时方向改变，否则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

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

为了兴趣，也为了保持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