package com.company;


import java.util.*;

class Solution {

    // 参考了下面的解法:
    // https://discuss.leetcode.com/topic/68773/java-solution
    // 开始没有用dp,超时了
    // discuss里面解法太牛逼了,用位图来作为key记录
    // 用Boolean而不是boolean来做数组,可以充分利用null的初始值
    // 其中 ^= 异或也用的非常好,非常到位,返回的时候也很好

    Boolean[] gotList;
    int m;
    int key;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1+maxChoosableInteger)*maxChoosableInteger < desiredTotal) {
            return false;
        }

        m = maxChoosableInteger;
        key = 0;
        gotList = new Boolean[1 << m];
        return win(desiredTotal);

    }

    private boolean win(int d) {
        if (gotList[key] != null) {
            return gotList[key];
        }
        for (int i=0; i<m; i++) {
            int bit = 1 << i;
            if ((key & bit) == 0) {
                if (i+1 >= d) {
                    gotList[key] = true;
                    return true;
                }

                key ^= bit;
                boolean tmp = false;
                if (!win(d-i-1)) {
                    tmp = true;
                }
                key ^= bit;
                if (tmp) {
                    gotList[key] = true;
                    return true;
                }
            }
        }
        gotList[key] = false;
        return false;
    }

}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");
        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:
        int maxChoosableInteger = 18;
        int desiredTotal = 79;
        boolean ret = solution.canIWin(maxChoosableInteger, desiredTotal);
        System.out.printf("ret:%b\n", ret);

        System.out.println();

    }

}