Python程序：求解砖块移除游戏中最大得分

假设Amal和Bimal正在玩一个游戏。他们有一个数组nums，它确定了上面编号的n块砖块。在这个游戏中，玩家可以轮流从顶部移除一块、两块或三块砖块，并且移除的砖块上标明的数字会加到该玩家的分数中。如果Amal总是先开始，我们必须找到Amal最多能获得多少分数。

因此，如果输入类似nums = [1,2,3,4,5]，则输出为6，因为Amal可以选择移除砖块{1}、{1,2}或{1,2,3}。如果Amal选择前两块或三块砖块，那么Bimal可以取走所有剩余砖块并获得最高分，但如果Amal首先选择1，Bimal最多可以取走{2,3,4} = 9，而Amal可以取走5，所以Amal的总分为1+5 = 6。

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

  • INF := 9999
  • n := nums数组的大小
  • 反转列表nums
  • temp := 一个大小为n的数组，并用0填充
  • total := 一个大小为n的数组，并用0填充
  • 对于每个索引i和nums中的值val，执行以下操作：
    • total[i] := total[i-1] + val
  • temp[0] := nums[0]
  • temp[1] := temp[0]+nums[1]
  • temp[2] := temp[1]+nums[2]
  • 对于i从3到n-1的范围，执行以下操作：
    • a := nums[i]
    • b := nums[i] + nums[i-1]
    • c := nums[i] + nums[i-1] + nums[i-2]
    • temp[i] := a, b, c中的最大值
  • 返回temp[n-1]

示例

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

INF = 99999
def solve(nums):
   n = len(nums)
   nums.reverse()
   temp = [0]*n
   total = [0]*n
   for i, val in enumerate(nums):
      total[i] = total[i-1] + val
   temp[0] = nums[0]
   temp[1] = temp[0]+nums[1]
   temp[2] = temp[1]+nums[2]
   for i in range(3, n):
      a = nums[i]
      b = nums[i] + nums[i-1]
      c = nums[i] + nums[i-1] + nums[i-2]
      temp[i] = max(a, b, c)
   return temp[n-1]

nums = [1,2,3,4,5]
print(solve(nums))

输入

[1,2,3,4,5]

输出

6

更新于：2021年10月23日

浏览量：188

开启你的职业生涯

完成课程获得认证

开始学习
广告