问题描述
在 "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 <= 20
0 <= desiredTotal <= 300
解题思路
dfs
首先从递归的角度来思考,(事实上这里博弈的角度并没有那么强),第一个玩家选了x
,那么对下一个玩家而言,他的desiredTotal
就变成了desiredTotal - x
,而如果下一个玩家赢了,那么第一个玩家就输了。
状态压缩 + 记忆化搜索
首先注意到,这个题中maxChoosableInteger <= 20
,因此我们可以用一个最长不超过20位的二进制数mask
来表示数的选择过程,如果mask
的第i
位为1,说明i
还没有被选择过,即还能选;
同时我们可以注意到,desired_total
的值直接由mask
来决定,因为mask
的初始值为2^n - 1
,所以写cache
数组的时候无需加上desired_total
的维度;
注意位运算的优先级是很低的,建议加括号。
代码
class Solution {
public:
// 改写成位运算的形式
bool dfs(int desired_total, int cur_total, int bit20, int max_int, unordered_map<int, int> &ump) {
if (desired_total <= 0) {
return false;
}
if (bit20 == 0) {
return true;
}
if (ump.find(bit20) != ump.end()) {
return ump[bit20];
}
bool tmp = false;
int cnt = 1;
for (int i = max_int - 1; i >= 0; --i) {
if ((bit20 & (1 << i)) != 0) { // 说明数i + 1还没有被选
int mask = (bit20 ^ (1 << i));
tmp = tmp || (!dfs(desired_total - i - 1, cur_total + i + 1, mask, max_int, ump));
}
if (tmp) {
ump[bit20] = true;
return ump[bit20];
}
}
ump[bit20] = false;
return ump[bit20];
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= maxChoosableInteger) {
return true;
}
if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal)
return false;
unordered_map<int, int> ump;
int bit20 = (1 << maxChoosableInteger) - 1;
return dfs(desiredTotal, 0, bit20, maxChoosableInteger, ump);
}
};
标签:10,Medium,desiredTotal,464,我能,整数,玩家,int,maxChoosableInteger
From: https://www.cnblogs.com/zwyyy456/p/17172994.html