Can I Win

给两个数组,a和b, 两个人从[1,a]的正整数轮流取数, 不能取相同的数字, 不能取了就算输了, 两个人都是选择自己最佳方案, 求胜负.

看似博弈论, 起始就是便利所有可能, 没有优化的地方.

这题傻逼在于, 它非要让状态压缩, 就tm一个最大32个数字的boolean数组, 非让用bitmask压一下表示状态, 不然就TLE, 我真是服了

class Solution {
    public boolean canIWin(int m, int d) {
        Map<Integer, Boolean> memo = new HashMap<>();
        boolean[] visited = new boolean[m + 1];
        Arrays.fill(visited, false);
        if(m >= d)
            return true;
        if(m*(m+1) / 2 < d)
            return false;
        return dfs(memo, m, d, visited);
    }
    
    public int mask(boolean[] visited){
        int res = 0;
        for(int i = 0; i < visited.length; i++){
            if(visited[i]){
                res |= (1 << i);
            }
        }
        return res;//10100111
    }
    
    public boolean dfs(Map<Integer, Boolean> memo, int m, int d, boolean[] visited){
        if(d <= 0)
            return false;
        int encode = mask(visited);
        if(memo.containsKey(encode))
            return memo.get(encode);
        for(int i = 1; i <=m; i++){
            if(!visited[i]){
                visited[i] = true;
                boolean res = dfs(memo, m, d - i, visited);
                visited[i] = false;
                if(!res){
                     memo.put(encode, true);
                     return true;
                }
            }
        }
        memo.put(encode, false);
        return false;
    }
}