Algorithm

每日一题-石之游戏

[每日一题] (石之游戏)
n堆石头排成一行，你每次可以把相邻的2堆石头聚成1堆，聚合后的石头数会成为你的分数的一部分。
问当进行n-1次，所有石头聚成一堆后，怎么使得总分最小。
例子: [3, 4, 3]
  第一次 3+4=7 -> [7, 3]
  第二次 (7) + 7 + 3 = 17 -> [17]
  总分17最少。

Follow-up(Google onsite): 变成一个环

解题思路


使用动态规划,思路可参考算法导论的矩阵链乘法。
状态转移矩阵:
  p[i][j] = min[p[i][k] + p[k+1][j] + s[i][j]] (i<=k<=j)
  s[i][j] = s[i][k] + s[k+1][j]
其中p[i][j]表示从i合并到j所得的最小分数，s[i][j]表示从i合并到j所得出的数

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^3)
"""
stone = [16,11,7,17,11,7,9,2,17,20,22,7,5,17,6,14,21,2,9,2,15,20,14,6,12,16,9,8,14,5,1,12,4,19,5,14,22,20,13,12,19,14,3,6,17,21,13,17,8,9,18,1,8,12,5,20,2,7,14,22,14,7,12,20,22,2,13,15,9,14,20,13,3,18,8,10,20,10,18,21]
N = len(stone) 
class Solution(object):
    def stoneGame(self, stone, N):
        p = [[0 for i in xrange(N)] for j in xrange(N)] # p[i][j]代表合并i到j的最优解
        s = [[0 if i != j else stone[i] for i in xrange(N)] for j in xrange(N)] # s[i][j]代表合并i到j后生成的值
        for l in xrange(1, N): # 循环N-1次， 每次得到长度为l+1的石头堆的最优解
            for i in xrange(N-l):
                j = i + l # 计算当前尾部j
                p[i][j] = None
                for k in xrange(i, j):
                    if p[i][j] == None:
                        s[i][j] = s[i][k] + s[k+1][j]
                        p[i][j] = p[i][k] + p[k+1][j] + s[i][j]
                    else:
                        p[i][j] = min(p[i][j], p[i][k] + p[k+1][j] + s[i][j])
        return p[0][N-1] # p[0][N-1]代表合并0到N-1的最优解，即为答案