用Python在石头游戏中找到最高分的程序
假设有几块石头排成一排，这些石头中的每一个都有一个关联的数字，该数字在数组stoneValue中给出。在每一轮中，Amal将该行分成两部分，然后Bimal计算每个部分的值，即该部分中所有石头的值的总和。Bimal丢弃具有最大值的部分，Amal的分数增加剩余部分的值。当两个零件的值相同时，Bimal让Amal决定将哪个零件扔掉。下一轮从剩下的部分开始。当只剩下一颗石头时，游戏结束。我们必须找到Amal可以得到的最高分数。
所以，如果输入像stoneValue=[7,3,4,5,6,6]，那么输出将是
在第1轮，Amal像[7,3,4]、[5,6,6]一样划分行。左行的总和为14，右行的总和为17。Bimal扔掉了右行，Amal的分数现在是14。
在第2轮，Amal将行分成[7]、[3,4]。所以Bimal扔掉左边的一排，Amal的分数变成(14+7)=21。
在第3轮，Amal只有一种选择来划分行，即[3]、[4]。Bimal扔掉了右边的一排，Amal的分数现在是(21+3)=24。
示例
让我们看下面的实现来更好地理解
def solve(stoneValue):
def dfs(start, end):
if start >= end:
return 0
max_score = 0
for cut in range(start, end):
sum1 = partial_sum[start][cut]
sum2 = partial_sum[cut+1][end]
if sum1 > sum2:
score = sum2+dfs(cut+1, end)
elif sum1 < sum2:
score = sum1+dfs(start, cut)
else:
score = sum1+max(dfs(start, cut), dfs(cut+1, end))
max_score = max(score, max_score)
return max_score
def getPartialSum():
for i in range(n):
partial_sum[i][i] = stoneValue[i]
for i in range(n):
for j in range(i+1, n):
partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j]
n = len(stoneValue)
partial_sum = [[0]*n for _ in range(n)]
getPartialSum()
return dfs(0, n-1)
stoneValue = [7,3,4,5,6,6]
print(solve(stoneValue))输入
[7,3,4,5,6,6]输出结果
0