文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個表示分數的非負整數數組。
玩家 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 仍為贏家。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/predict-the-winner
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 464. 我能贏嗎（狀態壓縮+記憶化遞歸 / 博弈）
LeetCode 877. 石子游戲（DP）
LeetCode 1140. 石子游戲 II（DP）*
LeetCode 1406. 石子游戲 III（DP）
LeetCode 1563. 石子游戲 V（DP）
LeetCode 5447. 石子游戲 IV hard（博弈DP）
LeetCode 1025. 除數博弈（動態規劃）
LeetCode 5611. 石子游戲 VI（貪心）
LeetCode 5627. 石子游戲 VII（博弈DP）
天池 在線編程 雙向取數（博弈DP）

• dp[i][j] 表示剩余石子區間為 [i,j] 時，當前玩家與另一個玩家的最大分差

class Solution { public:bool PredictTheWinner(vector<int>& nums) {int n = nums.size(), i, j;vector<vector<int>> dp(n, vector<int>(n, INT_MIN));for(i = 0; i < n; ++i)dp[i][i] = nums[i];for(int len = 1; len < n; ++len){for(i = 0; i+len < n; ++i){dp[i][i+len] = max(nums[i]-dp[i+1][i+len], nums[i+len]-dp[i][i+len-1]);// 當前選手 拿左邊，減去下一個選手的分差； 拿右邊，減去下一個選手的分差}}return dp[0][n-1] >= 0;// 當前選手（先手）分差多或者等于，win} };

4 ms 8 MB

狀態空間只與上一行有關，可以壓縮，代碼略。

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 486. 预测赢家（博弈DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。