State Compression

上周参加了学校的acm比赛，只做出两道水题，看了答案发现其中有两道题用到了状态压缩，于是就去学习了一波。

状态压缩

状态压缩就是将题目的模型抽象成状态的集合，如果每个对象只有两个状态且对象数量较少，可以用0和1分别代表这两种状态，用一个二进制数可以表示所有对象的状态，其中位数等于对象的个数。状态压缩往往与动态规划联系起来，下面以LeetCode的一道题作为例子。

Can I Win

问题

你和小伙伴正在玩一个游戏，首先有1至n共n个数，你们轮流取一个数并对所有已经取出的数求和，如果大于m，那么最后取数的人获胜，取出的数不能重复。给出n和m，如果你先取数，并且双方均采取最佳策略，判断你最终能否获胜。

思路

首先这是一个双方博弈的过程，由于双方都采取最佳策略，那么只有在无论对方如何操作你都能获胜的情况下才算必胜。然后因为取出的数不能重复，所以需要存储这n个数的使用情况。如果用0表示未取出，1表示已取出，那么就可以用一个二进制数来表示取数状态，即状态压缩。最后用动态规划和深度优先搜索来求解。需要注意两种特殊情况：如果m小于或等于1，那么你必胜；如果m大于所有数的和，那么双方必败。

代码

// 判断n的第i位是否为1
bool is1(int n, int i) {
    return (n & 1 << i) != 0;
}

// 把n的第i位设置为1
int set1(int n, int i) {
    return n | (1 << i);
}

// 表示每种状态的胜负情况，0表示未确定，1表示必胜，-1表示必败
int dp[1 << 20] = {};

// m为最大数，t为求和目标，k为当前状态
bool dfs(int m, int t, int k) {
    if (t <= 0) return false;  // 若求和目标小于或等于0，说明前一个回合对方已经获胜，因此己方必败
    if (dp[k] != 0) return dp[k] > 0;  // 己方的胜负情况已确定

    for (int i = 0; i < m; ++i) {
        // 若状态中某一位不为1，说明对应的数未取出
        // 取出一个未取出的数，求和目标减去这个数，然后判断对方的胜负情况，如果对方必败，那么己方必胜
        if (!is1(k, i) && !dfs(m, t-i-1, set1(k, i))) {
            dp[k] = 1;
            return true;
        }
    }

    // 如果无论如何对方必胜，那么己方必败
    dp[k] = -1;
    return false;
}

bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if (desiredTotal <= 1) return true;  // 如果求和目标小于或等于1，你必胜
    int sum = maxChoosableInteger * (maxChoosableInteger+1) / 2;
    if (sum < desiredTotal) return false;  // 如果求和目标大于所有数的和，双方必败
    return dfs(maxChoosableInteger, desiredTotal, 0);
}

总结

状态压缩用二进制数表示状态，然后与动态规划结合求解，使复杂的问题简单化。虽然思路比较复杂，但非常有用，我还需要多做练习。