資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：求解磚塊移除遊戲中最大得分
假設Amal和Bimal正在玩一個遊戲。他們有一個數組nums，它確定了上面編號的n塊磚塊。在這個遊戲中，玩家可以輪流從頂部移除一塊、兩塊或三塊磚塊，並且移除的磚塊上標明的數字會加到該玩家的分數中。如果Amal總是先開始，我們必須找到Amal最多能獲得多少分數。
因此，如果輸入類似nums = [1,2,3,4,5]，則輸出為6，因為Amal可以選擇移除磚塊{1}、{1,2}或{1,2,3}。如果Amal選擇前兩塊或三塊磚塊，那麼Bimal可以取走所有剩餘磚塊並獲得最高分，但如果Amal首先選擇1，Bimal最多可以取走{2,3,4} = 9，而Amal可以取走5，所以Amal的總分為1+5 = 6。
為了解決這個問題，我們將遵循以下步驟
- INF := 9999
- n := nums陣列的大小
- 反轉列表nums
- temp := 一個大小為n的陣列，並用0填充
- total := 一個大小為n的陣列，並用0填充
- 對於每個索引i和nums中的值val，執行以下操作：
- total[i] := total[i-1] + val
- temp[0] := nums[0]
- temp[1] := temp[0]+nums[1]
- temp[2] := temp[1]+nums[2]
- 對於i從3到n-1的範圍，執行以下操作：
- a := nums[i]
- b := nums[i] + nums[i-1]
- c := nums[i] + nums[i-1] + nums[i-2]
- temp[i] := a, b, c中的最大值
- 返回temp[n-1]
示例
讓我們看看下面的實現以更好地理解：
INF = 99999 def solve(nums): n = len(nums) nums.reverse() temp = [0]*n total = [0]*n for i, val in enumerate(nums): total[i] = total[i-1] + val temp[0] = nums[0] temp[1] = temp[0]+nums[1] temp[2] = temp[1]+nums[2] for i in range(3, n): a = nums[i] b = nums[i] + nums[i-1] c = nums[i] + nums[i-1] + nums[i-2] temp[i] = max(a, b, c) return temp[n-1] nums = [1,2,3,4,5] print(solve(nums))
輸入
[1,2,3,4,5]
輸出
6
更新於：2021年10月23日
瀏覽量：188
廣告