用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
以上是 用Python在石头游戏中找到最高分的程序 的全部内容， 来源链接： utcz.com/z/322673.html
