Python实现石头游戏中最大得分程序

假设有一排石头，每块石头都有一个关联数字，这些数字存储在一个数组`stoneValue`中。在每一轮中，阿马尔将这排石头分成两部分，然后比马尔计算每一部分的值（该部分中所有石头的值的总和）。比马尔丢弃值最大的部分，阿马尔的得分增加剩余部分的值。当两部分的值相同时，比马尔让阿马尔决定丢弃哪一部分。下一轮以剩余部分开始。当只剩下一块石头时，游戏结束。我们需要找到阿马尔可以获得的最大得分。

因此，如果输入类似于`stoneValue = [7,3,4,5,6,6]`，则输出为：

  • 第一轮，阿马尔将这一排石头分成两部分：[7,3,4]，[5,6,6]。左边部分的总和是14，右边部分的总和是17。比马尔丢弃右边部分，阿马尔的得分现在是14。

  • 第二轮，阿马尔将这一排石头分成两部分：[7]，[3,4]。比马尔丢弃左边部分，阿马尔的得分变为(14 + 7) = 21。

  • 第三轮，阿马尔只有一次选择来划分这一排石头，即[3]，[4]。比马尔丢弃右边部分，阿马尔的得分现在是(21 + 3) = 24。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数`dfs()`。它将接收起始位置`start`和结束位置`end`。

  • 如果`start >= end`，则

    • 返回0

  • `max_score := 0`

  • 对于`cut`从`start`到`end`的范围，执行以下操作：

    • `sum1 := partial_sum[start, cut]`

    • `sum2 := partial_sum[cut+1, end]`

    • 如果`sum1 > sum2`，则

      • `score := sum2 + dfs(cut+1, end)`

    • 否则，如果`sum1 < sum2`，则

      • `score := sum1 + dfs(start, cut)`

    • 否则，

      • `score := sum1 + max(dfs(start, cut), dfs(cut+1, end))`

    • `max_score := max(score, max_score)`

  • 返回`max_score`

  • 定义一个函数`getPartialSum()`。它将接收

  • 对于`i`从0到`n - 1`的范围，执行以下操作：

    • `partial_sum[i, i] := stoneValue[i]`

  • 对于`i`从0到`n - 1`的范围，执行以下操作：

    • 对于`j`从`i+1`到`n - 1`的范围，执行以下操作：

      • `partial_sum[i, j] := partial_sum[i, j-1] + stoneValue[j]`

  • 在主方法中，执行以下操作：

  • `n := stoneValue`的大小

  • `partial_sum :=`一个大小为n x n的二维数组，并填充为0

  • `getPartialSum()`

  • 返回`dfs(0, n-1)`

示例

让我们看看下面的实现以更好地理解

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

更新于：2021年10月6日

235 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告