0464. Can I Win
===============
题目信息
--------
:题号: 0464
:难度: Medium
:主题: 两人博弈、不重复整数、累计总和、先手必胜
:原题: `LeetCode 0464 `_
:重点: 每个整数最多选择一次、谁先使累计和达到或超过目标谁获胜、双方采用最优策略
题目重述
--------
两名玩家轮流从整数集合 ``1..maxChoosableInteger`` 中选择一个尚未使用的整数,并把它加入共享累计总和。第一个使累计总和达到或超过 ``desiredTotal`` 的玩家立即获胜,先手玩家先行动。
判断双方都采用最优策略时,先手玩家是否能够保证获胜。``maxChoosableInteger`` 位于 ``[1, 20]``,``desiredTotal`` 位于 ``[0, 300]``。每个整数整局只能使用一次;若所有可选整数之和仍小于目标,则任何玩家都无法达到目标,先手不能保证获胜。
自建示例
--------
先手存在必胜开局:
.. code-block:: text
输入:maxChoosableInteger = 4,desiredTotal = 6
输出:true
解释:先手选择 1。无论对手随后选择 2、3 或 4,先手都能选择一个尚未使用的数,使累计和达到或超过 6。
所有整数总和不足:
.. code-block:: text
输入:maxChoosableInteger = 3,desiredTotal = 7
输出:false
解释:1 + 2 + 3 = 6,小于目标 7,整局不可能有人达到目标。
位掩码记录已使用整数
--------------------
因为最大可选整数不超过 20,可以用一个整数的第 ``i`` 位表示数字 ``i + 1`` 是否已经被使用。一个掩码代表一个确定的局面;轮到当前玩家时,若选择某个数能立即达到目标就获胜,否则把该数标记后交给对手,只要存在一个让对手无法获胜的选择,当前局面就是必胜。
先判断所有数字总和是否足够达到目标;若不足,任何策略都不可能获胜。递归参数中的当前和随掩码唯一确定,但显式传入可使转移含义清楚。
C++ 实现
--------
.. code-block:: cpp
class Solution {
int maximum;
int target;
std::vector memo;
bool win(int used, int current) {
int& cached = memo[used];
if (cached != -1) return cached;
for (int i = 0; i < maximum; ++i) {
if (used & (1 << i)) continue;
int value = i + 1;
if (current + value >= target ||
!win(used | (1 << i), current + value)) {
return cached = 1;
}
}
return cached = 0;
}
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if (desiredTotal <= 0) return true;
long long sum = static_cast(maxChoosableInteger) *
(maxChoosableInteger + 1) / 2;
if (sum < desiredTotal) return false;
maximum = maxChoosableInteger;
target = desiredTotal;
memo.assign(1 << maximum, -1);
return win(0, 0);
}
};
代码分析
--------
``memo[used]`` 缓存的是“从该使用集合出发、轮到当前玩家时能否获胜”,如果存在立即获胜或能把对手送入必败局面的选择就返回真;所有选择都失败时才返回假。状态数为 ``2^m``,每个状态尝试 ``m`` 个数字,时间复杂度为 ``O(m 2^m)``,空间复杂度为 ``O(2^m)``。