在Python中找到游戏中可收集的最大点数的程序

在Python中找到游戏中可收集的最大点数的程序

假设我们玩一款纸牌游戏。我们用一个数字线性排列给出若干张卡片。卡片上的数字是随机分布的;在卡片的开头和结尾,插入两张数字为1的卡片。现在,在游戏中,我们必须通过拿起给定的卡片来收集最大的得分。卡片在数组“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
  • 在列表卡片的开头和结尾分别插入值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]))

输入

[7, 5, 9, 10]

输出

1025

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程