在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。

为了解决这个问题，我们将按照以下步骤进行 –

n：石头的大小
dp：大小为n的数组，填充为0
对于i在n-1到0的范围内，递减1，做以下操作
- v：= stones [i]
- run_sum：= 0
- 对于j在i + 1到n-1的范围内，做以下操作
  - new_run：= run_sum + stones[j]
  - dp [j]：=（new_run-dp [j]）和（run_sum + v-dp [j-1]）的最大值
  - run_sum：= new_run
返回dp [n-1]

例子

让我们看一下以下实现，以更好地理解-

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))