有一個這樣的小游戲：
多個不同顏色的方塊位于一列，你每次可以消除一片連續(xù)的相同顏色的方塊，并獲得得分｛連續(xù)方塊的個數(shù)^2｝。
消除完后右邊的方塊移動過來。
問，怎樣玩才能使得分最高？
這是一道黑書上面的題目。我想了n久想不出來。。
黑書的解法是動態(tài)規(guī)劃，時間復(fù)雜度為O(N^4)，空間復(fù)雜度為O(N^3)。
覺得挺有意思的，就把它的方法實現(xiàn)了一下。
# 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)