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 := stones的大小
  • dp := 一个大小为n的数组，并用0填充
  • 对于从n - 1到0的i，递减1，执行以下操作：
    • v := stones[i]
    • run_sum := 0
    • 对于从i + 1到n - 1的j，执行以下操作：
      • 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))

输入

[6,4,2,5,3]

输出

8

更新于: 2021年10月6日

135 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告