1.題目
在 "100 game" 這個游戲中，兩名玩家輪流選擇從 1 到 10 的任意整數，累計整數和，先使得累計整數和 達到或超過 100 的玩家，即為勝者，
如果我們將游戲規則改為 “玩家 不能 重復使用整數” 呢？
例如，兩個玩家可以輪流從公共整數池中抽取從 1 到 15 的整數（不放回），直到累計整數和 >= 100，
給定兩個整數 maxChoosableInteger （整數池中可選擇的最大數）和 desiredTotal（累計和），若先出手的玩家是否能穩贏則回傳 true ，否則回傳 false ，假設兩位玩家游戲時都表現 最佳 ，
示例 1：
輸入：maxChoosableInteger = 10, desiredTotal = 11
輸出：false
解釋：
無論第一個玩家選擇哪個整數，他都會失敗，
第一個玩家可以選擇從 1 到 10 的整數，
如果第一個玩家選擇 1，那么第二個玩家只能選擇從 2 到 10 的整數，
第二個玩家可以通過選擇整數 10（那么累積和為 11 >= desiredTotal），從而取得勝利.
同樣地，第一個玩家選擇任意其他整數，第二個玩家都會贏，示例 2:
輸入：maxChoosableInteger = 10, desiredTotal = 0
輸出：true示例 3:
輸入：maxChoosableInteger = 10, desiredTotal = 1
輸出：true
提示:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
2.思路
這道題資料范圍比較小，可以想到是狀態壓縮的情況，但是狀態十分復雜，我是參考題解想的，一個數拿回不能放回，即只能使用一次，因此需要使用一個資料結構記錄狀態，C++和Java都可以使用Map作為記錄，狀態就是當前這個數有沒有使用，使用的話這一位就為1；如100是3，第i位為1表示i被使用，
如果是先手必輸的話 應該是 所有情況都是后手必勝；如果是先手必勝的話 是存在一種情況是后手必輸
3.代碼
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(((1+maxChoosableInteger)*maxChoosableInteger*0.5)<desiredTotal)
return false;
return dfs(maxChoosableInteger,0,desiredTotal,0);
}
bool dfs(int maxChoosableInteger, int userNumbers, int desiredTotal, int currentTotals)
{
if(memory.count(userNumbers)==0)
{
bool res=false;
for(int i=0;i<maxChoosableInteger;i++)
{
int temp=((userNumbers>>i)&1);
if( temp==0)
{
int sum=i+1+currentTotals;
if(sum>=desiredTotal)
{
res=true;
break;
}
//判斷對方是否輸
int x=userNumbers |(1<<i);
int total=currentTotals+i+1;
if(!dfs(maxChoosableInteger,x,desiredTotal,total))
{
res=true;
break;
}
}
}
memory.insert({userNumbers,res});
}
return memory.find(userNumbers)->second;
}
map<int,bool> memory;
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/536033.html
標籤：其他