有一个这样的小游戏：
多个不同颜色的方块位于一列，你每次可以消除一片连续的相同颜色的方块，并获得得分｛连续方块的个数^2｝。
消除完后右边的方块移动过来。
问，怎样玩才能使得分最高？
这是一道黑书上面的题目。我想了n久想不出来。。
黑书的解法是动态规划，时间复杂度为O(N^4)，空间复杂度为O(N^3)。
觉得挺有意思的，就把它的方法实现了一下。
# Block Game
blocks = [(1,2), (2,4), (3,5), (1,2), (3,6), (1,9), (2,10)]
best = {}
choose = {}
def sqr(x):
return x*x
def dfs(i, j, k):
if j < i:
return 0
if (i, j, k) in best:
return best[(i, j, k)]
m = [(sqr(k + blocks[j][1]) + dfs(i, j - 1, 0), j)]
for p in range(i, j):
if blocks[p][0] == blocks[j][0]:
m += [(dfs(i, p, k + blocks[j][1]) + dfs(p + 1, j - 1, 0), p)]
best[(i, j, k)], choose[(i, j, k)] = max(m)
return best[(i, j, k)]
def show(i, j, k, s):
if j < i:
return
#print 'show', i, j, k, blocks
c = choose[(i, j, k)]
if c == j:
s += sqr(blocks[c][1])
print blocks, 'remove', c, ':', blocks[c], 'score', s
del blocks[c]
show(i, j - 1, 0, s)
else:
show(c + 1, j - 1, 0, s)
v = blocks[c + 1][1]
blocks[c] = (blocks[c][0], blocks[c][1] + v)
del blocks[c + 1]
show(i, c, v, s)
dfs(0, len(blocks) - 1, 0)
show(0, len(blocks) - 1, 0, 0)