在Python中找到石头游戏分数的最小差异的程序
假设我们有一个名为stones的数组，其中stones[i]表示从左数第i个石头的值。两个朋友Amal和Bimal用这些石头玩回合制游戏，Amal总是先开始。n块石头排成一排。每个玩家可以从行中移除最左边的石头或最右边的石头，并获得等于该行中剩余石头值总和的分数。谁将获得更高的分数将获胜。现在，Bimal发现他将永远输掉这场比赛，因此他决定将比分的差异降到最低。Amal的目标是最大化得分的差异。所以我们必须找到Amal和Bimal得分的差异，如果他们都发挥最佳。
所以，如果输入像stones=[6,4,2,5,3]，那么输出就是6，因为Amal可以取3，所以他的分数是6+4+2+5=17，Bimal的分数0到目前为止，数组就像[6,4,2,5]，然后Bimal取6所以他的分数4+2+5=11，现在数组是[4,2,5]。然后Amal移除4，所以他的分数17+2+5=24，石头阵列[2,5]Bob移除2，所以他的分数11+5=16，当前的石头阵列[5]并且Amal移除最后一个值为5的石头得了0分，所以他最后的分数是24+0=24，所以他们的分数差是24-16=8。
示例
让我们看看以下实现以获得更好的理解-
def solve(stones):
n = len(stones)
dp = [0] * n
for i in range(n - 1, -1, -1):
v = stones[i]
run_sum = 0
for j in range(i + 1, n):
new_run = run_sum+stones[j]
dp[j] = max(new_run - dp[j], run_sum+v - dp[j - 1])
run_sum = new_run
return dp[n - 1]
stones = [6,4,2,5,3]
print(solve(stones))输入
[6,4,2,5,3]输出结果
8