Python程序:找出游戏中可收集的最大点数


假设我们正在玩一个纸牌游戏。我们得到几张线性排列的牌,每张牌上都有一个数字。卡片上的数字是随机分布的;在卡片的开头和结尾,插入了两张数字为 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
    • 对于 z 从 x + 1 到 y,执行
      • temp := (temp, search(x, z) + search(z, y) + cards[x] * cards[z] * cards[y]) 的最大值
    • 返回 temp
  • 分别在列表 cards 的开头和结尾插入值 1 和 1
  • 返回 search(0, cards 的大小 - 1)

示例

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

Open Compiler
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]))

输入

[7, 5, 9, 10]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

1025

更新于: 2021年10月16日

208 次浏览

开启你的 职业生涯

完成课程获得认证

立即开始
广告