题目
464.
我能赢吗
在 "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
相似题目
题解
【我能赢吗】我能赢
记忆化搜索
最多可选 20 个数，可以使用一个 int
表示哪些数字选过，哪些数字没选过，然后 dfs
枚举搜索即可，当数字超过给定的界限或者向下搜索发现对方不能赢，那我就能赢！
不难想到函数签名可以是
dfs(player, score, state)，参数分别表示玩家，分数，和 int
表示的已经选择过的数字的状态，但实际上根据最后一个参数状态是可以反推玩家和分数的，所以可以化简为
dfs(state)，仅状态即可。
当然，若是直接搜索，时间复杂度会是 \(O(n!)\), 其中 \(n\) 是最大可选数字（即第一步有 \(n\) 种选择，第二步有 \(n - 1\)
种选择，依次类推，按照乘法原理可得），即 \(20!
= 2432902008176640000 = 2.4 \times
10^{18}\)，显然是无法接受的，处理方法为使用记忆化搜索的方法避免重复状态的搜索，此时最多会有
\(2^{20} = 1,048,576\)
种状态，可以接受！（对每一个数字只有已选择和未选择两种可能，共 20
个数字）。
最后需要特别注意的是，若所有数字累加都达不到要求，那么要返回
false，这里需要特殊处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:
return False
@cache
def dfs(sc, state):
""" 当前分数，当前状态, 返回当前玩家能不能赢 """
select = 2 << (maxChoosableInteger - 1)
ad = maxChoosableInteger
while select > 1:
if (state & select) == 0:
if sc + ad >= desiredTotal or not dfs(sc + ad, state | select):
return True
select >>= 1
ad -= 1
return False
return dfs(0, 0)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution {
static int[] dp = new int[1 << 21];
int mci, dt;
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
return false;
Arrays.fill(dp, -1);
mci = maxChoosableInteger;
dt = desiredTotal;
return dfs(0, 0);
}
public boolean dfs(int sc, int state) {
if (dp[state] == -1) {
for (int i = mci, select = 2 << (mci - 1); i >= 1; --i, select >>= 1) {
if ((state & select) == 0) {
if (sc + i >= dt || !dfs(sc + i, state | select)) {
dp[state] = 1;
break;
}
}
}
if (dp[state] == -1) dp[state] = 0;
}
return dp[state] == 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
return false;
vector<int> dp(1 << maxChoosableInteger + 1, -1);
return dfs(dp, maxChoosableInteger, desiredTotal, 0, 0);
}
bool dfs(vector<int>& dp, int mci, int dt, int sc, int state) {
if (dp[state] == -1) {
for (int i = mci, select = 2 << (mci - 1); i >= 1; --i, select >>= 1) {
if ((state & select) == 0) {
if (sc + i >= dt || !dfs(dp, mci, dt, sc + i, state | select)) {
dp[state] = 1;
break;
}
}
}
if (dp[state] == -1) dp[state] = 0;
}
return dp[state] == 1;
}
};
|
- 时间复杂度: \(O(2 ^ n \times n)\),
\(n\) 表示最大可选数字即
maxChoosableInteger
- 空间复杂度: \(O(2 ^ n)\)