英文原文
In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.
What if we change the game so that players cannot re-use integers?
For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.
Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.
Example 1:
Input: maxChoosableInteger = 10, desiredTotal = 11 Output: false Explanation: No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.
Example 2:
Input: maxChoosableInteger = 10, desiredTotal = 0 Output: true
Example 3:
Input: maxChoosableInteger = 10, desiredTotal = 1 Output: true
Constraints:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
中文题目
在 "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），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
通过代码
高赞题解
先读懂题意：
“稳赢”指的是，假设有两个人A, B，A先抽整数然后轮到B，再轮到A…，每次都根据要凑的和选择最有利于自己赢的数（并不一定越大越好，所以说是一种博弈），如果存在A走一步之后, B无论怎么走能还是A能赢的情况，那么就说A能稳赢（而不是所有的情况下）。
例如maxChoosableInteger = 10,desiredTotal=3 那么就存在A抽3，然后B抽其他数都赢不了的情况，因为A已经赢了（可以理解为B就不用再抽了）,所以A可以稳赢。
又如：maxChoosableInteger = 10，desiredTotal = 11 那么A第一轮选1(此时选得越小就越有利于自己赢),那么第二个玩家可以选择10（此时选择11-1就有利于自己赢）来赢得胜利，那么A就不能稳赢了。
下面提供两种解法（解决的思路一致，见注释）
法1：记忆化回溯
public class Solution {
/**
* 记忆化回溯（也称为递归+备忘录），自顶向下
* 采用记忆化后的时间复杂度为O(2^n)(如果不进行记忆的话，时间复杂度将是O(n!))，可以理解为已经缩成了只有一个分支了
* 然后为什么要进行记忆化：
* 因为我们发现，例如[2,3]和[3,2]之后的玩家选择状态都是一样的，都是可以从除了2,3之外的
* 数字进行选择，那么就可以对选择2和3后第一个玩家能不能赢进行记忆存储
* 这里采用state[]数组存储每个数字是否都被选过，选过则记录为1，然后我们将state.toString()
* 使得[2,3]和[3,2]它们的结果都是一样的"0011"，作为key，存储在HashMap中，value是选了2和3
* 之后第一个玩家是否稳赢
* @param maxChoosableInteger
* @param desiredTotal
* @return
*/
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true;
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; //1,..maxChoosable数列总和都比目标和小
int[] state = new int[maxChoosableInteger + 1]; //state[1]=1表示1被选了
return backtraceWitMemo(state, desiredTotal, new HashMap<String, Boolean>());
}
private boolean backtraceWitMemo(int[] state, int desiredTotal, HashMap<String, Boolean> map) {
String key = Arrays.toString(state); //这里比较关键，如何表示这个唯一的状态，例如[2,3]和[3,2]都是"0011"，状态一样
if (map.containsKey(key)) return map.get(key); //如果已经记忆了这样下去的输赢结果,记忆是为了防止如[2,3]，[3,2]之后的[1,4,5,..]这个选择区间被重复计算
for (int i = 1; i < state.length; i++){
if (state[i] == 0){ //如果这个数字i还没有被选中
state[i] = 1;
//如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了
if (desiredTotal - i <= 0 || !backtraceWitMemo(state, desiredTotal - i, map)) {
map.put(key, true);
state[i] = 0; //在返回之前回溯
return true;
}
//如果不能赢也要记得回溯
state[i] = 0;
}
}
//如果都赢不了
map.put(key, false);
return false;
}
}
法2：状压DP(DFS+记忆)
(这里需要一些位操作知识，我把涉及到的位运算原因都写了出来)
/**
* @Description:
* 由于状态不可用数组进行传递【在递归当中会受到改变，不能准确定位当前状态】，故在此处用Int的位表示状态（1表示用过,0表示未用过）
* 这里采用DP状态压缩的方式，思想与回溯类似，只是这里的状态被压缩成了一个bitArray了
* 状态压缩，我们可以用二进制的第i位的0或者1来表示i这个数字的选取与否，这样所有数字的选取状态就可以用一个数来很方便的表示，
* 题目说了不超过20位，所以这里就可以用一个int来表示状态state，通过state来判断状态是否一致，进而进行记忆化的存取
*/
public class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true;
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
/**
* dp表示"每个"取数(A和B共同作用的结果)状态下的输赢
* 例如只有1,2两个数选择，那么 (1 << 2) - 1 = 4 - 1 = 3种状态表示：
* 01,10,11分别表示：A和B已经选了1，已经选了2，已经选了1、2状态下，A的输赢情况
* 并且可见这个表示所有状态的dp数组的每个状态元素的长度为maxChoosableInteger位的二进制数
*/
Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1];
return dfs(maxChoosableInteger, desiredTotal, 0, dp);
}
/**
* @param maxChoosableInteger 选择的数的范围[1,2,...maxChoosableInteger]
* @param desiredTotal 目标和
* @param state 当前状态的十进制表示（记录着可能不止一个数被选择的状态）
* @param dp 记录所有状态
* @return
*/
private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) {
if (dp[state] != null)
return dp[state];
/**
* 例如maxChoosableInteger=2，选择的数只有1,2两个，二进制只要两位就可以表示他们的选择状态
* 最大位为2（第2位），也就是1 << (2 - 1)的结果，所以最大的位可以表示为 1 << (maxChoosableInteger - 1)
* 最小的位可以表示为 1 << (1 - 1)，也就是1（第1位）
* 这里i表示括号的范围
*/
for (int i = 1; i <= maxChoosableInteger; i++){
//当前待抉择的位，这里的tmp十进制只有一位为1，用来判断其为1的位，对于state是否也是在该位上为1
//用以表示该位（数字）是否被使用过
/**
* (&运算规则，都1才为1)
* 例如,i=3, tmp = 4, state = 3;
* 100
* &011
* =0 表示该位没有被使用过，也就是第三位没有被使用过，即数字3 (i)没有被使用过
*/
int tmp = (1 << (i - 1));
if ((tmp & state) == 0){ //该位没有被使用过
//如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了,tmp|state表示进行状态的更新
/**
* 例如
* 100
* |011
* =111
*/
//注意这里并没有像回溯一样进行状态的(赋值化的)更新、回溯
//其实这里是隐含了回溯的，我们通过参数传递更新后的state
//但是我们在这个调用者这里的state还是没有进行更新的，所以
//就相当于回溯了状态。
if (desiredTotal - i <= 0 || !dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) {
dp[state] = true;
return true;
}
}
}
//如果都赢不了
dp[state] = false;
return false;
}
}
有不足的地方，欢迎指正
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 11939 | 33685 | 35.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 翻转游戏 II | 中等 |
| 猜数字大小 II | 中等 |
| 预测赢家 | 中等 |
