algorithm - 动态规划 : States in a 2-player game

Question

这是 problem在编程比赛中我在哪里“发现”了如何在 2 人游戏中通过各个州。

问题是:在两个玩家 A 和 B 之间玩另一种游戏，其中 A 总是先开始并从给定的矩阵中选择一些字母并从给定的字典中造词。然后丢弃这些字母。下一位玩家从剩下的字母中选择。最后一个说不出话的人就输了。每个都发挥最佳效果。

来自editorial我在这里引用

    To iterate over all non-empty subsets of the given 
    set when they represented using bitmasks:

    submask = mask
    while submask > 0
        // do the job with the submask
        submask = (submask - 1) AND mask

在我看到的解决方案之一中

    int solve(int state)
    {
        if(dp[state]!=-1)
            return(dp[state]);

        int res=1;
        int nstate=state;
        while(1)
        {
            if(valid[nstate])
                res=solve(state&(~nstate));
            if(res==0)
                break;
            nstate=((nstate-1)&state);
            if(nstate==0)
                break;
        }
        if(res==0)
            dp[state]=1;
        else
            dp[state]=0;
        return(dp[state]);
    }

此代码有另一个 AND 和 ~。

我不明白这里的“状态”是什么，以及这个 AND 如何带我们穿越所有状态？请解释一下。

Answer 1

状态说明

状态是剩余字母的集合。

我们用 1 替换仍然存在的字母，用 0 替换已经消失的字母。

这会产生一个二进制数，它是变量掩码中保存的数字。

例如，假设我们在游戏开始时有字母 ABCDEFGH，而在某一时刻我们只剩下字母 B 和 D。

数字 0x50 代表当前状态:

ABCDEFGH  at start
-B-D----  at current point in game
01010000  replace with 1's for letters we still have
0x50      treat as a binary number

一点点转动

两种解决方案都使用位旋转 nstate=((nstate-1)&state) 。

如果您以 nstate=state 开头，此代码将生成状态的所有子集。

这是什么意思？好吧，假设我们有当前字母 B 和 D 的状态。这个状态的所有可能的非空子集是 {B,D},{B},{D}。

这些将由二进制数 01010000,01000000,00010000 表示。

而且我们可以看到，这些确实是通过执行下面的Python代码生成的:

state=0b01010000
nstate=state
while nstate:
    print bin(nstate)
    nstate=(nstate-1)&state

给出输出:

0b01010000
0b01000000
0b00010000   

为什么会这样？

粗略地说，代码使用nstate = nstate-1 对所有可能的二进制数进行递减计数，而& state 会跳过刚刚发生变化的部分在我们不关心的位中(通过立即将它们设置为零，而不是等待它们倒数到零)。