?LeetCode刷題實戰(zhàn)464：我能贏嗎

輸入：
maxChoosableInteger = 10
desiredTotal = 11

輸出：
false

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

class?Solution?{
public:
????bool?canIWin(int?maxChoosableInteger, int?desiredTotal)?{
????????if?(maxChoosableInteger >= desiredTotal) return?true;
????????if?(maxChoosableInteger * (maxChoosableInteger + 1) / 2?< desiredTotal) return?false;
????????unordered_map<int, bool> m;
????????return?canWin(maxChoosableInteger, desiredTotal, 0, m);
????}
????bool?canWin(int?length, int?total, int?used, unordered_map<int, bool>& m)?{
????????if?(m.count(used)) return?m[used];
????????for?(int?i = 0; i < length; ++i) {
????????????int?cur = (1?<< i);
????????????if?((cur & used) == 0) {
????????????????if?(total <= i + 1?|| !canWin(length, total - (i + 1), cur | used, m)) {
????????????????????m[used] = true;
????????????????????return?true;
????????????????}
????????????}
????????}
????????m[used] = false;
????????return?false;
????}
};