刚看到这道题时没有什么思路，想想常用的算法（套路），可能的方法有 动态规划 或者 递归 ，好的，上网搜索大神的解法。
如果想让第一个人赢，就需要第二个人输。那么什么时候第二个人输呢？
static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0) return true;
const int sum = (1 + maxChoosableInteger) * maxChoosableInteger >> 1;
if (sum < desiredTotal) return false;
vector<char> mem (1 << maxChoosableInteger);
function<bool(int, int, int)> helper =
[&] (int m, int d, int state) {
if (d <= 0) return false;
if (mem[state]) return mem[state] == 1;
for (int i = 0; i < m; ++i) {
if (state & (1 << i)) continue;
if (!helper(m, d - (i + 1), state | (1 << i))) {
mem[state] = 1;
return true;
}
}
mem[state] = -1;
return false;
};
return helper(maxChoosableInteger, desiredTotal, 0);
}
};
注意，代码开始部分的判断desiredTotal是否小于0， 以及所有可选的数字的和是否大于desiredTotal非常重要，我们一定要判断是否一定会有一个赢家，才能进入后面的程序，因为后面的程序判断某一个人赢的条件是另一个人输，如果两个人都输，后面的程序会认为某一个人赢。