难度中等370收藏分享切换为英文接收动态反馈
在 “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
思路
首先想到的是暴力解法，也就就将每一种情况都遍历一遍。其实动态规划，也是在记忆dfs的基础上进行的，也就是其中一个是正向遍历(自顶向下)，一个是递归逆向的(自底向上)。
那么怎么去记忆化。也就是找到变量并将其记录下来，下次再次遇到的时候就可以直接得到结果。
这里的变量是，
- 我们取的数和剩余的数(这里用二进制去表示取的数，因为m<=20,也就是20位，这样就可以用statae代表，而visited[state]记录着这个状态下的结果)
- sum
依照这个思路写下代码如下；
class Solution {
private:
// visited[i] == 0，说明没有计算过
// visited[i] == 1，说明计算过，结果为 true
// visited[i] == 2，说明计算过，结果为 false
int visited[1 << 21];
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
// 判断当前做选择的玩家（先手），是否一定赢
// 开始时，state = 0，表示「公共整数集」中的所有数字都未被使用过
if (maxChoosableInteger >= desiredTotal)
return true;
if (maxChoosableInteger * (maxChoosableInteger + 1) < 2*desiredTotal)
return false;
return dfs(0, 0, maxChoosableInteger, desiredTotal);
}
// 当前做选择的玩家是否一定赢
bool dfs(int state, int sum, int maxChoosableInteger, int desiredTotal) {
if (visited[state] == 1) return true;
if (visited[state] == 2) return false;
// 遍历可选择的公共整数
for (int x = 1; x <= maxchoosableinteger; ++x) { 如果 x 已经被使用过了，则不能选择 if ((1 << x) & state) continue; 如果选择了 以后，大于等于了 desiredtotal，当前玩家赢 (sum +>= desiredTotal) {
visited[state] = 1;
return true;
}
// 当前玩家选择了 x 以后，判断对方玩家一定输吗？
if (!dfs((1 << x) | state, sum + x, maxChoosableInteger, desiredTotal)) {
visited[state] = 1;
return true;
}
}
visited[state] = 2;
return false;
}
};
