Java&C++题解与拓展——leetcode464.我能赢吗【不太懂的记忆化搜索与状态压缩】

• 题目要求
• 思路一：博弈论DP（超时）
• • Java
  • C++
• 思路二：状态压缩
• • Java
  • C++
• 总结

• 用记忆化搜索记录状态，判断当前回合能否赢；
• 定义一个二进制数 s t a t e state state表示可选择的数；
• 定义递归函数DFS(state, tot, k)，参数分别为当前状态、当前累加和、当前轮数：
  • k k k从 0 0 0开始，所以偶数表示先手；
  • 计算当前轮是否能达到最终状态，先手赢后手输，也就是偶数轮返回 1 1 1，奇数轮返回 − 1 -1 −1。
• 判定最终结果，是否稳赢，即DFS(0, 0, 0)是否为 1 1 1。

class Solution {
    int mci, dt;
    int[][] f = new int[1 << 20][2];
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        this.mci = maxChoosableInteger;
        this.dt = desiredTotal;
        if(dt == 0)
            return true;
        return DFS(0, 0, 0) == 1;
    }
    // 1赢、-1输
    int DFS(int state, int tot, int k) {
        if(state == ((1 << mci) - 1) && tot < dt) // 全用过还不到
            return -1;
        if(f[state][k % 2] != 0)
            return f[state][k % 2];
        int res = k % 2 == 0 ? 1 : -1; // 偶数轮（先手）赢，奇数轮输
        for(int i = 0; i < mci; i++) {
            if(((state >> i) & 1) == 1) // 已用过
                continue;
            if(tot + i + 1 >= dt) // 当前轮数赢
                return f[state][k % 2] = res;
            if(DFS(state | (1 << i), tot + i + 1, k + 1) == res)
                return f[state][k % 2] = res;
        }
        return f[state][k % 2] = -res;
    }
}

• 时间复杂度： O ( 2 n + 1 × n ) O(2^{n +1}times n) O(2n+1×n)，其中 n n n为最大可选数字（maxChoosableInteger）
• 空间复杂度： O ( 2 n + 1 ) O(2^{n +1}) O(2n+1)

class Solution {
    int mci, dt;
    int f[1 << 20][2];
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        this->mci = maxChoosableInteger;
        this->dt = desiredTotal;
        if(dt == 0)
            return true;
        if(mci * (mci + 1) / 2 < dt)
            return false;
        return DFS(0, 0, 0) == 1;
    }
    // 1赢、-1输
    int DFS(int state, int tot, int k) {
        if(f[state][k % 2] != 0)
            return f[state][k % 2];
        int res = k % 2 == 0 ? 1 : -1; // 偶数轮（先手）赢，奇数轮输
        for(int i = 0; i < mci; i++) {
            if(((state >> i) & 1) == 1) // 已用过
                continue;
            if(tot + i + 1 >= dt) // 当前轮数赢
                return f[state][k % 2] = res;
            if(DFS(state | (1 << i), tot + i + 1, k + 1) == res)
                return f[state][k % 2] = res;
        }
        return f[state][k % 2] = -res;
    }
};

• 时间复杂度： O ( 2 n + 1 × n ) O(2^{n +1}times n) O(2n+1×n)，其中 n n n为最大可选数字（maxChoosableInteger）
• 空间复杂度： O ( 2 n + 1 ) O(2^{n +1}) O(2n+1)

• 不记录轮数维度，极短当前状态能否获胜
• 调整重点

  将记录『原始回合的先后手发起 与 原始回合的先后手获胜情况』调整为『当前回合发起 和 当前回合获胜情况』。

class Solution {
    int mci, dt;
    int[] f = new int[1 << 20];
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        this.mci = maxChoosableInteger;
        this.dt = desiredTotal;
        if(mci * (mci + 1) / 2 < dt)
            return false;
        if(dt == 0)
            return true;
        return DFS(0, 0) == 1;
    }
    // 1赢、-1输
    int DFS(int state, int tot) {
        if(f[state] != 0)
            return f[state];
        for(int i = 0; i < mci; i++) {
            if(((state >> i) & 1) == 1) // 已用过
                continue;
            if(tot + i + 1 >= dt) // 当前轮数赢
                return f[state] = 1;
            if(DFS(state | (1 << i), tot + i + 1) == -1) // 对方输
                return f[state] = 1;
        }
        return f[state] = -1;
    }
}

• 时间复杂度： O ( 2 n × n ) O(2^ntimes n) O(2n×n)，其中 n n n为最大可选数字（maxChoosableInteger）
• 空间复杂度： O ( 2 n ) O(2^n) O(2n)

class Solution {
    int mci, dt;
    int f[1 << 20];
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        this->mci = maxChoosableInteger;
        this->dt = desiredTotal;
        if(dt == 0)
            return true;
        if(mci * (mci + 1) / 2 < dt)
            return false;
        return DFS(0, 0) == 1;
    }
    // 1赢、-1输
    int DFS(int state, int tot) {
        if(f[state] != 0)
            return f[state];
        for(int i = 0; i < mci; i++) {
            if(((state >> i) & 1) == 1) // 已用过
                continue;
            if(tot + i + 1 >= dt) // 当前轮数赢
                return f[state] = 1;
            if(DFS(state | (1 << i), tot + i + 1) == -1) // 对方输
                return f[state] = 1;
        }
        return f[state] = -1;
    }
};

• 时间复杂度： O ( 2 n × n ) O(2^ntimes n) O(2n×n)，其中 n n n为最大可选数字（maxChoosableInteger）
• 空间复杂度： O ( 2 n ) O(2^n) O(2n)

……懂了但没完全懂的一道题，在纸上用例子顺一遍过程才看懂，对记忆化搜索和状态转移压缩的思路总是不能捋得很通顺，需要加强。

第二种方法的优化原理其实并没有很理解，下次遇到还是不会做。为什么要优化掉轮数这个参数，优化掉为什么状态总数就少了一半。