LeetCode 486. Predict the Winner / 464. Can I Win

[Woodyiiiiiii]

486. Predict the Winner

486. Predict the Winner

类似题目：
464. Can I Win

---

这道题是博弈的题型，两个玩家都会play optimally，类似模拟题，所以用上递归/DP去选择对于当前玩家最优的路径。

因为首先是player 1去选择，所以以player 1的视角开始，判断他能获得的最大值。最大值获取dfs函数两种可能，一种是取数组最左边的，另一种取数组最右边的，而因为到下一个玩家选择时，他肯定也会选择对于他的最大值，所以对之前的player来说他只能选择下下轮他能获取的最小值。

class Solution {

    int[] nums;

    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        int sum = dfs(0, n - 1);
        if (sum >= total - sum) {
            return true;
        } else {
            return false;
        }
    }

    private int dfs(int l, int r) {
        if (l > r) {
            return 0;
        }
        int c1 = nums[l] + Math.min(dfs(l + 2, r), dfs(l + 1, r - 1));
        int c2 = nums[r] + Math.min(dfs(l, r - 2), dfs(l + 1, r - 1));
        return Math.max(c1, c2);
    }
}

---

464. Can I Win

No.464 同理。先预处理，接着用位表示只能取一次的特殊性。然后判断当前和是否满足期望值，是则说明之前上个玩家已经成功了，所以当前玩家失败(所以要预处理以免没有上个玩家)；否则，遍历取值，计算所有可能性，如果都是真，说明下个玩家肯定会赢，只能返回输，否则有一线生机，返回赢，因为是最优选择(play optimally)。

这道题最后还要用记忆化，否则超时。

class Solution {
    Map<String, Boolean> memo;
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int total = 0;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            total += i;
        }
        if (total < desiredTotal) {
            return false;
        }
        if (desiredTotal == 0) {
            return true;
        }
        memo = new HashMap<>();
        int mask = (1 << maxChoosableInteger) - 1;
        return dfs(mask, desiredTotal, maxChoosableInteger, 0);
    }

    private boolean dfs(int mask, final int dt, final int mc, int sum) {
        if (sum >= dt) {
            return false;
        }
        String key = mask + " " + sum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        for (int i = 0; i < mc; i++) {
            if (((mask >> i) & 1) == 1) {
                boolean ans = dfs(mask ^ (1 << i), dt, mc, sum + i + 1);
                if (!ans) {
                    memo.put(key, true);
                    return true;
                }
            }
        }
        memo.put(key, false);
        return false;
    }
}