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