石子歸并
有一個(gè)石子歸并的游戲。最開始的時(shí)候梆造，有n堆石子排成一列缴守，目標(biāo)是要將所有的石子合并成一堆葬毫。合并規(guī)則如下：
每一次可以合并相鄰位置的兩堆石子
每次合并的代價(jià)為所合并的兩堆石子的重量之和
求出最小的合并代價(jià)。
樣例
對(duì)于石子序列：[4, 1, 1, 4]（每個(gè)數(shù)代表這堆石子的重量）屡穗，最優(yōu)合并方案下贴捡，合并代價(jià)為 18：
- 合并第2堆和第3堆 => [4, 2, 4], 代價(jià) +2
- 合并前兩堆 => [6, 4]，代價(jià) +6
- 合并剩下的兩堆 => [10]村砂，代價(jià) +10
其他例子：
[1, 1, 1, 1] 代價(jià)為 8
[4, 4, 5, 9] 代價(jià)為 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]
