文章目錄
- 題目
- 解題思路
- 動態規劃
- 狀態定義
- 狀態轉移方程
- 我是傻*
- 代碼
題目
這兩道題的解題思路是一樣的，
877.石子游戲
亞歷克斯和李用幾堆石子在做游戲，偶數堆石子排成一行，每堆都有正整數顆石子 piles[i] ，
游戲以誰手中的石子最多來決出勝負，石子的總數是奇數，所以沒有平局，
亞歷克斯和李輪流進行，亞歷克斯先開始， 每回合，玩家從行的開始或結束處取走整堆石頭，
這種情況一直持續到沒有更多的石子堆為止，此時手中石子最多的玩家獲勝，假設亞歷克斯和李都發揮出最佳水平，當亞歷克斯贏得比賽時回傳 true ，當李贏得比賽時回傳 false ，
示例：
輸入：[5,3,4,5] 輸出：true 解釋： 亞歷克斯先開始，只能拿前 5 顆或后 5 顆石子 ， 假設他取了前 5 顆，這一行就變成了
[3,4,5] ， 如果李拿走前 3 顆，那么剩下的是 [4,5]，亞歷克斯拿走后 5 顆贏得 10 分， 如果李拿走后 5
顆，那么剩下的是 [3,4]，亞歷克斯拿走后 4 顆贏得 9 分， 這表明，取前 5 顆石子對亞歷克斯來說是一個勝利的舉動，所以我們回傳
true ，提示：
2 <= piles.length <= 500 piles.length 是偶數， 1 <= piles[i] <= 500 sum(piles) 是奇數，
486.預測贏家
給定一個表示分數的非負整數陣列， 玩家 1 從陣列任意一端拿取一個分數，隨后玩家 2 繼續從剩余陣列任意一端拿取分數，然后玩家 1 拿，……
，每次一個玩家只能拿取一個分數，分數被拿取之后不再可取，直到沒有剩余分數可取時游戲結束，最侄訓得分數總和最多的玩家獲勝，給定一個表示分數的陣列，預測玩家1是否會成為贏家，你可以假設每個玩家的玩法都會使他的分數最大化，
示例 1：
輸入：[1, 5, 2] 輸出：False 解釋：一開始，玩家1可以從1和2中進行選擇， 如果他選擇 2（或者 1 ），那么玩家 2 可以從
1（或者 2 ）和 5 中進行選擇，如果玩家 2 選擇了 5 ，那么玩家 1 則只剩下 1（或者 2 ）可選， 所以，玩家 1 的最終分數為
1 + 2 = 3，而玩家 2 為 5 ， 因此，玩家 1 永遠不會成為贏家，回傳 False ，示例 2：
輸入：[1, 5, 233, 7] 輸出：True 解釋：玩家 1 一開始選擇 1 ，然后玩家 2 必須從 5 和 7 中進行選擇，無論玩家
2 選擇了哪個，玩家 1 都可以選擇 233 ，
最終，玩家 1（234 分）比玩家 2（12 分）獲得更多的分數，所以回傳 True，表示玩家 1 可以成為贏家，提示：
1 <= 給定的陣列長度 <= 20. 陣列里所有分數都為非負數且不會大于 10000000 ， 如果最終兩個玩家的分數相等，那么玩家 1 仍為贏家，
解題思路
動態規劃
解讀：題目要求每個玩家，只能從當前陣列開頭或者結尾取，也就是說子陣列一定是連續的，相對原陣列而言不會出現斷層，
狀態定義
定義二維陣列 dp，其行數和列數都等于石子的堆數，dp[i][j] 表示當剩下的石子堆為下標 i 到下標 j 時，當前玩家與另一個玩家的石子數量之差的最大值，注意當前玩家不一定是先手 Alex，
狀態轉移方程
只有當i<=j時，剩下的石子堆才有意義，因此當i>j時，dp[i][j]=0；
當i=j，只剩下一堆石子，當前玩家只能取走這堆石子，因此對于所有0≤i≤len(nums)，都有dp[i][j]=nums[i]；
當i<j，當前玩家可以選擇取走nums[i]或者nums[j]，然后輪到另一個玩家在剩下的石子堆中取走石子，在兩種方案中，當前玩家會選擇最優的方案，使得自己的石子數量最大化，因此可以得到狀態轉移方程：dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])，最后判斷dp[0][-1]的值，如果大于0，則Alex的石子數量大于Lee的，回傳True，否則回傳False，
我是傻*
總是先手的贏，，，
代碼
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
l = len(piles)
dp = [[0]*l for _ in range(l)]
for i in range(l):
dp[i][i] = piles[i]
for i in range(l-2,-1,-1):
for j in range(i+1,l):
dp[i][j] = max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1])
return dp[0][-1]>=0
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
return True
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245280.html
標籤：其他