数据结构与算法学习笔记----状态压缩DP

@@ author: 明月清了个风
@@ first publish time: 2025.2.17

ps⭐️状态压缩动态规划（简称状态压缩DP）是一种通过压缩状态（一般为二进制）表示来优化动态规划的方法，常用于处理涉及组合状态的问题，如子集、排列或棋盘覆盖等。下面给出了两道经典例题，分别对应了棋盘覆盖模型和旅行商模型，第一题给出了代码优化的过程。

核心概念

状态压缩：使用位掩码（二进制数）等紧凑方式表示状态，如用二进制位表示元素是否被选中或位置是否被占据。
适用场景：问题状态包含多个独立元素的选择或排列，且规模较小（通常 $\le 20$ ）。

典型应用

旅行商问题（TSP）：用位掩码表示已访问城市，dp[mask][i]为访问mask中的城市后停在i的最短路径。
棋盘覆盖：如用1×2砖块铺满棋盘，状态表示当前行覆盖模式，逐行转移。
排列组合问题：如选数满足特定条件，用位掩码记录已选数。

优化技巧

预处理合法转移：提前生成状态间的合法转移，减少重复计算。
滚动数组：减少空间复杂度，如棋盘问题仅保留当前行和上一行状态。
位运算加速：利用位操作快速生成或检查状态。

Acwing 291. 蒙德里安的梦想

[原题链接](291. 蒙德里安的梦想 - AcWing题库)

求把 $\times M$ 的期盼分割成若干个 $\times 2$ 的长方形，有多少个方案。

例如，当 $N = 2, M = 4$ 时，共有 $5$ 种方案。当 $N = 2 ， M = 3$ 时共有 $3$ 种方案。

如下图所示：

在这里插入图片描述

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 $N$ 和 $M$ 。

当输入用例 $N = 0, M = 0$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$\le N,M \le 11$

思路

这一题的核心是：只看横着放的方块。因为当所有横着放的方块确定后，竖着放的也就确定了。总的方案数就等于只放横着的小方块的合法方案数。

如何判断合法？：因为剩下的方块都是竖着放的，因此按列来看，只要看连续的空格小方块是偶数个即可。

那么来看状态表示和状态计算。

状态表示使用f[i][j]表示已经将前 $i - 1$ 列摆好，且从第 $i - 1$ 列伸出到第 $i$ 列的状态是 $j$ 的所有方案，状态 $j$ 根据其二进制表示判断每个位置是否被占用。

状态计算也就是需要将上述表示进行划分，找到每个部分的前驱状态，同样的，根据最后一步的操作或者说状态进行划分，那么目前的状态f[i][j]在第 $i$ 列上的状态是 $j$ ，根据其二进制表示可以确定这一列的摆放情况，那么上一步的状态就是第 $i - 1$ 列的摆放情况 $k$ ，比如下图中第 $i$ 列的状态就是 $11001$ ，第 $i - 1$ 列的状态就是 $00110$ ，很明显这两个状态没有冲突的方格，因此合法，代码的实现就是j & k；第二个判断的地方就是第 $i$ 列的状态 $11001$ ，连续的空格小方块应是偶数个，否则无法放下竖着的小方块。

最终需要得到的结果是f[m][0]，表示已经将前 $m$ 列都摆好，并且伸出 $m + 1$ 列的状态为 $0$ ，也就是没有任何一行伸出去。

在这里插入图片描述

时间复杂度的计算就是 $状态量 \times 转移计算量$ ，状态量是二维 $11 \times 2^{11}$ ，因为最多有 $11$ 行嘛，二进制就是 $11$ 位，转移计算量又是 $2^{11}$ 次方，因此大概 $400$ 万的计算量。

中间的一步判断是否有连续偶数个空格我们可以提前进行处理，代码如下

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 12, M = 1 << N;int n, m;
long long f[N][M];
bool st[M];int main()
{while(cin >> n >> m, n || m){for(int i = 0; i < 1 << n; i ++) // 枚举所有状态，判断是否有连续奇数个空格{int cnt = 0;bool is_valid = true;for(int j = 0; j < n; j ++){if(i >> j & 1){if(cnt & 1) is_valid = false;cnt = 0;}else cnt ++;}if(cnt & 1) is_valid = false;  // 最后一段也要判断，循环里累加了但是会直接出来。st[i] = is_valid;}memset(f, 0, sizeof f);   // 每次清空DP数组。f[0][0] = 1;  // 表示前0列已经摆好，伸到第1列的为0的方案，也就是初始状态，只有1种。for(int i = 1; i <= m; i ++)  // 枚举二维状态for(int j = 0; j < 1 << n; j ++)for(int k = 0; k < 1 << n; k ++)  // 枚举前一列状态进行状态转移if((j & k) == 0 && st[j | k]) // 进行状态转移，判断i-1列和i列是否冲突，并且两列合法f[i][j] += f[i - 1][k];cout << f[m][0] <<endl;}return 0;
}

主要代码有三层循环，可以考虑优化，发现每次都需要枚举所有的 $1 << n$ 种前一列的状态，因此第三层循环可以直接放在外面预处理，也就是提前处理出所有对应 $k$ 的合法的 $j$ 状态，代码如下，速度大概可以快 $\sim 5$ 倍

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>using namespace std;const int N = 12, M = 1 << 12;int n, m;
long long f[N][M];
vector<int> state[M];
bool st[M];int main()
{while(cin >> n >> m, n || m){for(int i = 0; i < 1 << n; i ++){int cnt = 0;bool is_valid = true;for(int j = 0; j < n; j ++){if(i >> j & 1){if(cnt & 1)is_valid = false;cnt = 0;}else cnt ++;}if(cnt & 1) is_valid = false;st[i] = is_valid;}for(int i = 0; i < 1 << n; i ++){state[i].clear();for(int j = 0; j < 1 << n; j ++)if((i & j) == 0 && st[i | j])state[i].push_back(j);}memset(f, 0, sizeof f);f[0][0] = 1;for(int i = 1; i <= m; i ++)for(int j = 0; j < 1 << n; j++)for(auto k : state[j])f[i][j] += f[i - 1][k];cout << f[m][0] << endl;}return 0;
}

Acwing 91. 最短Hamilton路径

[原题链接](91. 最短Hamilton路径 - AcWing题库)

给定一张 $n$ 个点的带权无向图，点从 $\sim 1$ 标号，求起点 $0$ 到终点 $n - 1$ 的最短Hamilton路径。

Hamilton路径的定义是从 $0$ 到 $n - 1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$ 。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a [i, j]$ ）。

对任意的 $x, y, z$ ，数据保证 $a [x, x] = 0, a [x, y] = a [y, x]$ 并且 $\ge a[x, z]$ 。

输出格式

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

数据范围

$\le n \le 20$ ,

$\le a[i, j] \le 10^7$

思路

首先思考暴力做法，其实就是经过所有的点一次，因此就是一个全排列，但是很明显会超时，也就是方案数过多，当暴力搜索无法满足时，考虑使用动态规划，这里就是状态压缩DP，因为对于每个点都可以看成二进制的一位，用一个整数就可以表示所有的点的状态。

对于状态表示，使用f[i][j]表示所有从 $0$ 号点走到 $j$ 号点的并且走过的点由 $i$ 表示（二进制表示每个点的状态）的方案，属性是求最小值。

对于状态转移，这里根据倒数第二个点是哪个点进行状态划分，比如上一个点是 $k$ ，那么当前的路径状态就是 $\rarr k \rarr j$ ，也就是先从 $0$ 走到 $k$ 再走到 $j$ ，那么 $i$ 中就要先去掉 $j$ 这个点，也就是 $f[i - {j}][k] + a[k][j]$ ，注意这里的状态 $i$ 中一点要有 $j$ 和 $k$ 两个点才行，代码也比较简单

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 20, M = 1 << N;int n;
int w[N][N];
int f[M][N];int main()
{cin >> n;for(int i = 0; i < n; i ++)for(int j = 0; j < n; j ++)cin >> w[i][j];memset(f, 0x3f, sizeof f);f[1][0] = 0;for(int i = 0; i < 1 << n; i++)for(int j = 0; j < n; j ++)if(i >> j & 1)for(int k = 0; k < n; k ++)if((i - (1 << j)) >> k & 1)f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);cout << f[(1 << n) - 1][n - 1] << endl;return 0;
}