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)

示例

讓我們看看以下實現以更好地理解 -

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

更新於: 2021年10月16日

208 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

立即開始
廣告