回溯之博弈论：我能赢吗

464. 我能赢吗

概念介绍

今天学习到了两个新的概念「状态压缩」和「记忆化搜索」

• 状态压缩：利用二进制来表示当前状态。其原理就是把元素的使用情况抽象成一种状态，其实现方式为如果第i个元素被使用了，就把状态的第i位标记为1，反之则为0
• 记忆化搜索：一般记忆化搜索都是结合「状态压缩」来使用，说白了就是暴力搜索存在「重叠子问题」，利用「备忘录 emeo」来记录状态的结果

虽然这两个名词是我今天第一次弄明白意思，但是这两个方法的思想在之前经常使用！！在文章「经典回溯算法：集合划分问题」和「回溯算法：单词拆分」均有使用这两种方法

问题分析

问题详情可见 我能赢吗

首先来介绍「博弈论」和「回溯算法」是如何相结合滴！！关于回溯算法的详细介绍可见 回溯(DFS)

其实如果回溯的题目做多了之后，就可以对这一类题目的套路有更加深刻的理解。也就是文章 回溯(DFS) 里面说的需要搞清楚「路径」「选择」「结束条件」三个要素！

回到这个题目上面来，对于「先手」和「后手」来说，只有次序的不一样，其他部分完全一致

每个人每次的「选择」即为从n个数中选择一个，但有一个前提：已经被选过的数无法再被选择，所以需要一个标记

简简单单的画一下这个问题的「回溯树」吧！！

代码实现

下面给出完整的代码

// 记录状态的结果
// 1 表示 true；-1 表示 false
private int[] emeo;
private int maxChoosableInteger;
private int desiredTotal;
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    // 如果所有数之和小于 desiredTotal
    if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
    // 初始化，注意数组大小为 1 << maxChoosableInteger
    // 原因：n 个数，一共有 2^n 种状态
    emeo = new int[1 << maxChoosableInteger];
    this.maxChoosableInteger = maxChoosableInteger;
    this.desiredTotal = desiredTotal;
    return dfs(0, 0) == 1;
}
// state 记录的是 n 个数字的使用情况
// 若第 i 个数字被使用，那么 state 中第 i 为 1
private int dfs(int state, int curTotal) {
    // 该状态已经有结果，直接返回
    if (emeo[state] != 0) return emeo[state];
    // 选择列表
    for (int i = 0; i < maxChoosableInteger; i++) {
        // 已经被使用，跳过
        if (((state >> i) & 1) == 1) continue;
        // 胜利
        if (curTotal + i + 1 >= desiredTotal) {
            emeo[state] = 1;
            break;
        }
        // 后手若为 false，等价于 先手胜利
        if (dfs(state | (1 << i), curTotal + i + 1) == -1) {
            emeo[state] = 1;
            break;
        }
    }
    // n 个数遍历完，如果 emeo[state] = 0，说明先手无法获得胜利
    // 所以直接置 emeo[state] = -1
    if (emeo[state] == 0) emeo[state] = -1;
    return emeo[state];
}