leetcode464. Can I Win

题目要求

In the "100 game," two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input: maxChoosableInteger = 10 desiredTotal = 11

Output: false

Explanation: No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.

现在有1～n这n个整数，两个人轮流从这n个数中任意选1个数（数字不能重复选择），假如两个人都用最优方法来选取数字，问玩家一是否一定能够获胜。

思路和代码

像这种轮流选择的题目，其实通过深度优先遍历的方式来穷尽所有的结果，就一定可以的得出结论。但是穷尽可能会出现O(n!)的时间复杂度并导致超市，因此尽可能的记录过程中得出的结论就可以提高时间复杂度。

这题的中间过程有哪些呢：

1. 剩余还没有选择的数字
2. 想要得到的目标数字

但是其实我们可以知道，2可以通过（1～n）的数字和减去所有已经选择的数字得出，因此我们只要记录中间结果1即可。而中间结果如何记录呢？可以通过位式图来记录每一位被选择的情况，以及这种选择情况是否一定能够让第一个选择的玩家获胜。举个例子，如1～5，其中选中了（1，3），则位式图为00101.

代码如下：

    Map<Integer, Boolean> map = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        int sum = (maxChoosableInteger + 1) * maxChoosableInteger / 2;
        if (sum < desiredTotal) return false;
        boolean[] selected = new boolean[maxChoosableInteger+1];
        return helper(desiredTotal, selected);
    }

    public boolean helper(int desiredTotal, boolean[] selected) {
        if (desiredTotal <= 0) return false;
        int symbol = format(selected);
        if (map.containsKey(symbol)) {
            return map.get(symbol);
        }
        int size = selected.length;
        for (int i = 1 ; i< size ; i++) {
            if (!selected[i]) {
                selected[i] = true;
                if (!helper(desiredTotal-i, selected)) {
                    selected[i] = false;
                    map.put(symbol, true);
                    return true;
                }
                selected[i] = false;
            }
        }
        map.put(symbol, false);
        return false;
    }

    public int format(boolean[] selected) {
        int symbol = 0;
        for (boolean select : selected) {
            symbol <<= 1;
            if (select) {
                symbol |= 1;
            }
        }
        return symbol;
    }