文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

在 “100 game” 這個游戲中，兩名玩家輪流選擇從 1 到 10 的任意整數，累計整數和，先使得累計整數和達到或超過 100 的玩家，即為勝者。

如果我們將游戲規則改為 “玩家不能重復使用整數” 呢？

例如，兩個玩家可以輪流從公共整數池中抽取從 1 到 15 的整數（不放回），直到累計整數和 >= 100。

給定一個整數 maxChoosableInteger （整數池中可選擇的最大數）和另一個整數 desiredTotal（累計和），判斷先出手的玩家是否能穩贏（假設兩位玩家游戲時都表現最佳）？

你可以假設 maxChoosableInteger 不會大于 20， desiredTotal 不會大于 300。

示例： 輸入： maxChoosableInteger = 10 desiredTotal = 11 輸出： false 解釋： 無論第一個玩家選擇哪個整數，他都會失敗。 第一個玩家可以選擇從 1 到 10 的整數。 如果第一個玩家選擇 1，那么第二個玩家只能選擇從 2 到 10 的整數。 第二個玩家可以通過選擇整數 10（那么累積和為 11 >= desiredTotal），從而取得勝利. 同樣地，第一個玩家選擇任意其他整數，第二個玩家都會贏。

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

2. 解題

類似題目：LeetCode 486. 預測贏家（博弈DP）

class Solution {unordered_map<int,bool> m; public:bool canIWin(int maxChoosableInteger, int desiredTotal) {if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal)return false;//總和不夠return win(maxChoosableInteger, desiredTotal, 0, 0);}bool win(int maxChoosableInteger, int desiredTotal, int point, int state) {if(m.find(state) != m.end())return m[state];//重復的狀態，直接讀取for(int i = 1; i <= maxChoosableInteger; i++){if(((state>>i)&1)==0){ // 該二進制位為0 表示沒有拿過該數if(point+i >= desiredTotal)return true;int newstate = state | (1<<i);//新的狀態，該位為1，用過了if(!win(maxChoosableInteger, desiredTotal, point+i, newstate))return m[state] = true;//上一個人在 newstate 下不能贏，那我在 state 狀態下能贏}}return m[state] = false;} };

508 ms 17.5 MB C++

---

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

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

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 464. 我能赢吗（状态压缩+记忆化递归 / 博弈）的全部內容，希望文章能夠幫你解決所遇到的問題。

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