用 Python 编写的寻找石头游戏最高分的程序

pythonserver side programmingprogramming更新于 2025/12/2 1:16:17

假设有几块石头排成一排，每块石头都有一个关联的数字，该数字在数组 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。

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

定义一个函数 dfs() 。这将需要开始、结束
如果开始 >= 结束，则
- 返回 0
max_score := 0
对于从开始到结束范围内的 cut，执行
- 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 + dfs(start, cut) 和 dfs(cut+1, end) 的最大值
- max_score := score 和 max_score 的最大值
返回 max_score
定义一个函数 getPartialSum() 。这将需要
对于范围在 0 到 n - 1 内的 i，执行
- partial_sum[i, i] := stoneValue[i]
对于范围在 0 到 n - 1 内的 i，执行
- 对于范围在 i+1 到 n - 1 内的 j，执行
  - 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))