Can I Win

动态规划法：

public class Solution {  
    HashMap<Integer, Boolean> map = new HashMap<>();  
    boolean[] dp;  
    public boolean canIWin(int max, int desired) {  
        int sum = (1 + max) * max / 2;  
        if (sum < desired) return false;  
        if (desired <= 0) return true;  
        dp = new boolean[max];  
        return helper(desired);  
    }  
    private boolean helper(int desired) {  
        if (desired <= 0) return false;  
        int key = format();  
        if (map.containsKey(key)) return map.get(key);  
        for (int i = 0; i < dp.length; i++) {  
            if (!dp[i]) {  
                dp[i] = true;  
                if (!helper(desired - i - 1)) {  
                    map.put(key, true);  
                    dp[i] = false;  
                    return true;  
                }  
                dp[i] = false;  
            }  
        }  
        map.put(key, false);  
        return map.get(key);  
    }  
    private int format() {  
        int res = 0;  
        for (int i = 0; i <= dp.length - 1; i++) {  
            if (dp[i]) {  
                res |= (1 << i);  
            }  
        }  
        return res;  
    }  
}

DFS暴力法：

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal<=0) return true;
        //如果1到最大能选的值所有和都不能满足目标值，那么肯定失败
        if (maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return false;
        char state[] = new char[maxChoosableInteger];
        for(int i=0;i<maxChoosableInteger;i++) state[i] = '0';
        return dfs(desiredTotal, state, new HashMap<>());
    }
    private boolean dfs(int total, char[] state, HashMap<String, Boolean> hashMap) {
        String key= new String(state);
        if (hashMap.containsKey(key)) return hashMap.get(key);
        for (int i=0;i<state.length;i++) {
            if (state[i]=='0') {
                state[i]='1';
                if (total<=i+1 || !dfs(total-(i+1), state, hashMap)) {
                    hashMap.put(key, true);
                    state[i]='0';
                    return true;
                }
                state[i]='0';
            }
        }
        hashMap.put(key, false);
        return false;
    }
}

递归法：

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        unordered_map<int, bool> m;
        return canWin(maxChoosableInteger, desiredTotal, 0, m);
    }
    bool canWin(int length, int total, int used, unordered_map<int, bool>& m) {
        if (m.count(used)) return m[used];
        for (int i = 0; i < length; ++i) {
            int cur = (1 << i);
            if ((cur & used) == 0) {
                if (total <= i + 1 || !canWin(length, total - (i + 1), cur | used, m)) {
                    m[used] = true;
                    return true;
                }
            }
        }
        m[used] = false;
        return false;
    }
};