用Python在石头游戏中找到最高分的程序

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

示例

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

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