Python程式，用於檢查第一個人是否可以透過獲取最大分數來贏得糖果遊戲

假設兩位玩家正在玩遊戲。在一條線上放置了幾顆糖果，第一個人得到一個稱為nums的數字列表，該列表表示每顆糖果的點數。在每個人的回合中，他們可以從線的前面挑選1、2或3顆糖果，然後將其從列表中刪除，並將它們的總點數加到他們的分數中。當所有糖果都被刪除時，遊戲將結束，得分較高的人將獲勝。我們必須檢查第一個人是否可以贏得這場比賽。

因此，如果輸入類似於nums = [1, 1, 2, 3, 50]，則輸出將為True，因為第一個人可以取1顆糖果，然後另一名玩家必須取1、2或3顆糖果。無論哪種情況，第一個人都可以取點數為50的糖果。

為了解決這個問題，我們將遵循以下步驟：

  • n := nums的大小

  • table := 一個包含三個0的陣列。

  • 對於i從n-1到0，遞減1，執行以下操作

    • profit := -inf

    • sum_val := 0

    • 對於j從i到min(i+3, n)，執行以下操作

      • sum_val := sum_val + nums[j]

      • profit := max(profit, (sum_val - table[j-i]))

    • 設定table := 一個包含三個值的列表[profit, table[0], table[1]]

  • 當table[0] > 0時返回true，否則返回false

讓我們看看下面的實現以獲得更好的理解：

示例

 線上演示

import math
class Solution:
   def solve(self, nums):
      n = len(nums)
      table = [0, 0, 0]
      for i in range(n − 1, −1, −1):
         profit = −math.inf
         sum_val = 0
         for j in range(i, min(i + 3, n)):
            sum_val += nums[j]
            profit = max(profit, sum_val − table[j − i])
         table[:] = [profit, table[0], table[1]]
      return table[0] > 0
ob = Solution()
nums = [1, 1, 2, 3, 50]
print(ob.solve(nums))

輸入

[1, 1, 2, 3, 50]

輸出

True

更新於: 2020-12-26

272 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始
廣告