用 Python 编写程序，找出游戏中可收集的最大分数

pythonserver side programmingprogramming更新于 2026/1/11 16:44:17

假设我们正在玩纸牌游戏。我们得到了几张线性排列的纸牌，每张纸牌上都有一个数字。纸牌上的数字是随机分布的；在纸牌的开头和结尾，插入了两张上面写着数字 1 的纸牌。现在，在游戏中，我们必须通过拿起给定的纸牌来收集最大分数。纸牌以数组"cards"表示，数组中的元素代表 cards[i] 的数量。当我们拿起纸牌 i 时，我们收集的分数为 cards[i - 1] * cards[i] * cards[i + 1]。当我们拿起一张纸牌时，cards[i - 1] 和 cards[i] 成为邻居。因此，从这些给定的卡片中，我们可以找出可以收集的最大分数。

因此，如果输入为 cards = [7, 5, 9, 10]，则输出将为 1025

因此在游戏中，我们可以拾取 −

索引 1 处的卡片并获得 7 * 5 * 9 = 315 分。

新索引 1 处的卡片并获得 7 * 9 * 10 = 630 分。

索引 1 处的卡片并获得 7 * 10 = 70 分。

最后一张卡片并获得 10 分。

总分 = 315 + 630 + 70 + 10 = 1025

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

定义一个函数 search() 。这将需要 x、y
- temp := 0
- 对于范围为 x + 1 到 y 的 z，执行
  - temp := (temp、search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y]) 的最大值
- 返回 temp
在列表 cards 的开头和结尾分别插入值 1 和 1
返回 search(0, cards 的大小 - 1)

示例

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

def solve(cards):
   def search(x, y):
      temp = 0
      for z in range(x + 1, y):
         temp = max(temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y])
      return temp
   cards = [1] + cards + [1]
   return search(0, len(cards) - 1)

print(solve([7, 5, 9, 10]))