状态压缩动态动态规划算法指的是把记录动态规划中“状态”的集合转化为整数的一类算法。

在动态规划的每个阶段，我们需要在动态规划的“状态”中记录若干个集合，来保存动态规划中的“轮廓”，以方便进行状态转移。若集合大小不超过 $N$，集合中的每个元素都是小于 $K$ 的自然数，则可以把这个集合看作一个 $N$ 位 $K$ 进制数，以一个 $[0, K^N-1]$ 之间的十进制证书的形式来进行状态存储。比较常用的是二进制的状态压缩。

最短Hamilton路径

问题

给定一张 $n(n \leq 20)$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 0 到终点 $n-1$ 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入描述：

第一行一个整数$n$。接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（一个不超过$10^7$ 的正整数，记为 $a[i,j]$）。对于任意的 $x,y,z$ ，数据保证 $a[x,x]=0，a[x,y]=a[y,x]$ 并且$a[x,y]+a[y,z] \geq a[x,z]$。

输出描述:

一个整数，表示最短 Hamilton 路径的长度。

分析

使用状态压缩的动态规划进行求解。$f[(1<<n)][n]$ 第一维使用了状态压缩表示了目前已经经历过节点，第二维表示，在该状态下最后访问的一个节点。

代码

int weight[20][20];
int f[1<<20][20];
int hamilton(int n) {
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i  < (1<<n); ++i) {
        for (int j = 1; j < n; ++j)  {
            if ((1<<j)&i) {
                for (int k = 0; k < n; ++k) {  // k从0开始
                        if (i&(1<<k))
                        f[i][j] = min(f[i][j], f[i^(1<<j)][k]+weight[k][j]);
                }
            }
        }
    }
    return f[(1<<n)-1][n-1];
}

Mondriaan’s Dream

问题

牛客网链接

简化后问题，求把高为 $h$ 宽为 $w$ $（1 <= h,w <= 11）$ 的棋盘分割成若干个宽和高分别为 1 和 2 的长方形，有多少种方案。

分析

从上向下对长方形进行填充，将行号作为阶段。将该行的填充状态作为 DP 的状态。$f[i][j]$ 表示填充到了第 $i$ 行，第 $i$ 行的填充状态为 $j$ 的情况下有多少种方案。$j$ 使用位压缩的形式。 $j$ 的 bit 位从低到高分别代表棋盘中该行从右到左的填充情况。若该格是平躺的长方形，或者是竖直长方形的下半部分，则为 0。若是竖直长方形的下班部分则为 1。

第 $j-1$行的形态 $k$ 能够转移到第 $i$ 行的形态 $j$，当且仅当：

$j$ 和 $k$ 执行按位与运算的结果是0。这保证了每个数字1的下方必须是数字0，代表继续补全竖着的1*2长方形。
$j$ 和 $k$ 执行按位或运算的结果的二进制表示中，每一段的连续的 0 都必须有偶数个。这些 0 代表若干个横着的1*2 长方形，奇数个 0 无法分割这种形态。

另集合 $S$ 表示所有符合每一段连续的0都是偶数的所有二进制数。则有状态转移方程。
$$
F[i,j] = \sum \limits_{j\&k=0\;and\;j|k\in S}F[i-1,k]
$$
初值：$F[0, 0] = 1$，其余为 0，目标：$F[N, 0]$

代码

int h, w;
long long f[12][1<<11];
int in_s[1<<11];

int main () {
    while (scanf("%d%d", &h, &w) == 2) {
        if (h == 0 || w == 0)
            break;
        for (int i = 0; i < (1<<w); ++i) {
            bool cnt = 0, has_odd = 0;
            for (int j = 0; j < w; j++) {
                if ((1<<j)&i) has_odd |= cnt, cnt = 0;
                else cnt^=1;
            }
            has_odd |= cnt;    // 处理最后一个
            in_s[i] = !has_odd;
        }
        f[0][0] = 1;   // 目标：f[h][0];
        for (int i = 1; i <= h; ++i) {
            for (int j = 0; j < (1<<w); ++j) {
                f[i][j] = 0;
                for (int k = 0; k < (1<<w); ++k) {
                    if (((j&k)==0) && in_s[j|k]) {        
                        f[i][j] += f[i-1][k];
                    }
                }
            } 
        }
        printf("%lld\n", f[h][0]);
    }
    return 0;
}

动态规划（六）状态压缩DP

Contents

最短Hamilton路径

Mondriaan’s Dream