LeetCode 464 - Can I Win

作者 QIFAN 日期 2017-01-18
LeetCode 464 - Can I Win

原题链接:464. Can I Win


题干

给定一个最大可选择数 max 和期望总和 total ,两个小伙伴玩游戏,轮流从 1 ~ max 中选择数字,不可重复选择,先使数字的和到达 total 的人赢。判断先走的玩家能不能赢。

max <= 20
total <= 300

举例
输入:
max = 10
total = 11
输出:false
解释:不管第一步走什么,第二步走的人都会赢。

思路

如果使用穷举法,那时间复杂度是 $O(max!)$ ,太大了,int 都放不下。

看一下是哪里重复了。1 ~ max 每个数字有两种选择,那最多是 $2^{max}$ 种状态。重复的状态是由于选择的次序不一样。

本文使用一个 boolean 数组表示每个状态,使用 HashMap 来存取状态,其中 key 是状态,值为能否达到 total 。但是 boolean[] 是对象,如果直接将其作为 key 存入,那只是一个 reference ,并不能代表真正的状态,如果每次都克隆,那花费又太大了。因为每个状态对应的是二进制,转换成十进制的范围是 0 ~ $2^{max - 1}$ 。那不如就转换成十进制作为 key 。

代码 cr Java solution using HashMap with detailed explanation ,使用自上而下的动态规划。

public class Solution {
Map<Integer, Boolean> map;
boolean[] used;
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 排除所有数字加起来也比 total 小的情况
int sum = (1+maxChoosableInteger)*maxChoosableInteger/2;
if(sum < desiredTotal) return false;
if(desiredTotal <= 0) return true;
map = new HashMap<>();
used = new boolean[maxChoosableInteger+1];
return helper(desiredTotal);
}
public boolean helper(int desiredTotal){
if(desiredTotal <= 0) return false;
int state = format(used);
if(!map.containsKey(state)){
// 尝试所有没有选择过的数字作为下一个
for(int i = 1; i < used.length; i++){
if(!used[i]){
used[i] = true;
// 如果我能达到 desire ,那意味着我的上一个不能达到 desire - i
if(!helper(desiredTotal - i)){
map.put(state, true);
used[i] = false;
return true;
}
used[i] = false;
}
}
map.put(state, false);
}
return map.get(state);
}
// transfer boolean[] to an Integer
public int format(boolean[] used){
int num = 0;
for(boolean b: used){
num <<= 1;
if(b) num |= 1;
}
return num;
}
}