ETH官方钱包

前往
大廳
主題

LeetCode - 0486. Predict the Winner 解題心得

Not In My Back Yard | 2024-03-18 12:00:07 | 巴幣 0 | 人氣 109

題目連結:


題目意譯:
你被給定一個整數陣列 nums。兩位玩家正在用這個陣列玩一個遊戲:他們分別是玩家 1 和玩家 2。

玩家 1 和玩家 2 輪流出手,而玩家 1 作為先手。兩位玩家一開始的分數值都是 0。在每一回合,現在輪到的玩家將可以從陣列兩端拿走其中一個元素(即 nums[0] 或 nums[nums.length - 1]),並且拿完之後陣列的大小將會減去 1。該玩家將會把選定的數字加到其分數值上。當陣列中沒有元素存在時,遊戲結束。

如果玩家 1 可以贏得遊戲,則回傳真(True)。如果兩玩家分數一樣,則玩家 1 依舊視為是贏家,而你也應回傳真。你可以假設兩位玩家都會按照最佳策略遊玩。

限制:
1 ≦ nums.length ≦ 20
0 ≦ nums[i] ≦ 10 ^ 7



範例測資:
範例 1:
輸入: nums = [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:
輸入: nums = [1,5,233,7]
輸出: true
解釋: 玩家 1 選擇 1。接著玩家 2 可以從 5 和 7 中選一個。無論玩家 2 的選擇,玩家 1 都可以選擇 233。
最終,玩家 1 的分數值(234)將會高於玩家 2 的(12),所以你需要回傳真,代表著玩家 1 可以獲勝。.


解題思維:
定義一個二維陣列 D,其中 D[i][j] 代表著當前陣列是原本的 nums[i] ~ nums[j] 時,「現在」的先手與「現在」的後手之分數值差最大可以多少。跟這種題目的遞迴式類似:
    D[i][i] = nums[i]、
    (上式為遞迴停止條件)
    D[i][j] = max(nums[i] - D[i + 1][j], nums[j] - D[i][j - 1]),其中 i ≠ j。

而遞迴完後,D[0][nums.length - 1] 即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作