石子归并
有一个石子归并的游戏。最开始的时候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并规则如下：
每一次可以合并相邻位置的两堆石子
每次合并的代价为所合并的两堆石子的重量之和
求出最小的合并代价。
样例
对于石子序列：[4, 1, 1, 4]（每个数代表这堆石子的重量），最优合并方案下，合并代价为 18：
- 合并第2堆和第3堆 => [4, 2, 4], 代价 +2
- 合并前两堆 => [6, 4]，代价 +6
- 合并剩下的两堆 => [10]，代价 +10
其他例子：
[1, 1, 1, 1] 代价为 8
[4, 4, 5, 9] 代价为 43
代码
class Solution:
"""
@param A: An integer array
@return: An integer
"""
def stoneGame(self, A):
# write your code here
if len(A) <= 0:
return 0
dp_now = [[0 for j in range(len(A))] for i in range(len(A))]
dp_sum = [[0 for j in range(len(A))] for i in range(len(A))]
for i in range(0, len(A)):
dp_now[i][i] = A[i]
dp_sum[i][i] = 0
for i in range(0, len(A)-1):
dp_now[i][i+1] = A[i] + A[i+1]
dp_sum[i][i+1] = A[i] + A[i+1]
if len(A) <= 2:
return dp_sum[0][-1]
for k in range(2, len(A)):
for i in range(0, len(A)-k):
j = i+k
for m in range(i, j):
if m == i:
dp_now[i][j] = dp_now[i][m] + dp_now[m+1][j]
dp_sum[i][j] = dp_now[i][m] + dp_now[m+1][j] + dp_sum[i][m] + dp_sum[m+1][j]
else:
dp_now[i][j] = min(dp_now[i][j], dp_now[i][m] + dp_now[m+1][j])
dp_sum[i][j] = min(dp_sum[i][j], dp_now[i][m] + dp_now[m+1][j] + dp_sum[i][m] + dp_sum[m+1][j])
return dp_sum[0][-1]
