相信在学完动态规划之后，就会接触到动态规划的许多进阶的版本，这里我将简单讲讲状压dp，顾名思义，状压，为什么叫状压~就是状态压缩，就是一种优化动态规划算法的技术，通常用于处理状态空间较大的问题。在状压动态规划中，我们会使用较小的数据结构来表示状态，并利用位运算来进行状态转移和计算，从而减少内存消耗和提高计算效率。具体来说，状压动态规划通常会使用整数来表示状态，其中整数的每一位对应于问题中的某种特定情况或特征。通过位运算，我们可以高效地表示和操作大量的状态，并且可以利用位运算的性质来进行状态转移和计算，从而减少时间和空间复杂度。状压动态规划通常用于处理状态空间较大的问题，例如组合优化问题、子集相关问题等。通过使用状压动态规划，我们可以更高效地解决这些问题，并且可以在一定程度上降低算法的时间复杂度和空间复杂度。
总的来说，状压动态规划是一种优化动态规划算法的技术，通过使用整数来表示状态并利用位运算来进行状态转移和计算，以提高算法的效率和性能。
在介绍完状压dp的概念之后，现在咱来回顾几个用得上的语法内容，因为在许多数据结构之中是用的比较少的。首先来回顾"<<"这是个什么？嗯，在C++中，<< 是位移运算符，用于将一个数的所有位向左移动指定的位数。在计算机编程中，左移运算符 << 不是表示数学上的指数运算，而是表示对数字进行位移操作。具体来说，对于整数 n，n << m 表示将 n 的二进制表示向左移动 m 位，相当于将 n 乘以 2 的 m 次幂。因此，1 << 20 表示将数字 1 左移 20 位，相当于将 1 乘以 2 的 20 次幂。这并不等同于数学上的指数运算，而是位运算的结果在这种情况下，1<<20 表示将整数1向左移动20位，相当于计算2的20次方，结果为1048576。表达式 2 << 10 表示将数字 2 左移 10 位。在计算机中，左移运算符 << 会将一个数的二进制表示向左移动指定的位数，相当于将这个数乘以 2 的指定次幂。因此，2 << 10 的结果是 2 乘以 2 的 10 次幂，即 2 的 10 次方，结果为 1024。
OK，<<相信大家了解差不多了吧，那现在就介绍"|":
在C++中，竖线（|）运算符代表按位或运算。它用于对两个整数的每个对应位执行逻辑或操作，返回的结果是两个数对应位上的逻辑或结果。例如，对于两个二进制数a和b，a | b将返回一个新的二进制数，其中每个位上的值是a和b对应位上值的逻辑或结果。
例如：
a = 5; // 二进制表示为 0101
b = 3; // 二进制表示为 0011
c = a | b; // c的值为 7，二进制表示为 0111
在上面的示例中，a | b的结果是7，因为在二进制表示中，对应的位上进行了逻辑或操作。
上文是一些基础知识，那回顾一下memset一个stl容器用于将一块内存空间设置为指定的值：一般的用法void *memset(void *ptr, int value, size_t num);
-
ptr是指向要设置值的内存起始地址的指针。 -
value是要设置的值，通常是一个无符号字符。 -
num是要设置的字节数。
这些东西回顾完了，其实在面对状压dp的时候的步骤和动态规划的差不多，只不过要多进行一个'|'操作进行状态压缩。干说是不是有点不太好理解下面上题目：
题目描述
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种 口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知 道每包内的糖果口味。
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖 果。
输入格式
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味
(对于 30% 的评测用例，1 ≤ N ≤ 20 。
对于所有评测样例，1 ≤ N ≤ 100，1 ≤ M ≤ 20，1 ≤ K ≤ 20，1 ≤ Ti ≤ M 。)
输出格式
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
样例输入
复制
6 5 3 1 1 2 1 2 3 1 1 3 2 3 5 5 4 2 5 1 2样例输出
复制
2
分析完题目，发现数据还挺好的咱可以用 n位二进制数来表示所购买糖果中 n 种口味的组合情况。
其中有1是不是就是代表有这个糖果，0就是没有？好好理解一下。
那咱怎样确定dp呢？嗯~既然要用01这种二进制来表示全部情况，我们可以用dp[i]：表示状态为i时所需的最小糖果包数。状态i表示口味的组合情况，每个口味对应状态中的一位。dp数组记录了每种口味组合所需的最小糖果包数，通俗一点讲用一个二进制数来表示口味的组合情况。比如，如果口味有4种，那么0001表示只包含口味1，1010表示包含口味2和口味4。dp[i]表示当口味组合为i时，所需的最小糖果包数。也就是说，dp数组记录了每种口味组合所需的最小糖果包数。
OK代码如下文章来源：https://www.toymoban.com/news/detail-853859.html
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 20;
int main() {
int n, m, k;
int dp[1 << MAX_N]; // 使用状压的数组需要开2^n，因为表示的是状态
int v[MAX_N]; // 记录每种糖果的口味状态
// 读入口味种类数n、糖果总种类数m、每种糖果的口味数k
cin >> n >> m >> k;
// 初始化dp数组为一个较大的数，表示无穷大
memset(dp, 0x3f, sizeof(dp));
// 读入每种糖果的口味状态
for (int i = 0; i < n; ++i) {
int flavors = 0;
for (int j = 0; j < k; ++j) {
int flavor;
cin >> flavor;
flavor--; // 口味从1开始，数组从0开始，需要减1
flavors |= (1 << flavor); // 使用按位或操作记录口味状态
}
dp[flavors] = 1; // 这些口味都可以用一包糖解决
v[i] = flavors; // 记录糖的状态
}
// 状态转移，枚举所有可能的状态
for (int i = 0; i < (1 << m); ++i) {
for (int j = 0; j < n; ++j) {
dp[i | v[j]] = min(dp[i | v[j]], dp[i] + 1); // 更新dp数组的值
}
}
// 输出结果
if (dp[(1 << m) - 1] == 0x3f3f3f3f) {
cout << -1; // 无法搭配出来
} else {
cout << dp[(1 << m) - 1]; // 搭配出来所需的最少糖果包数量
}
return 0;
}这样就通过一个状压dp解决啦这个题目，由于本人水平有限，有错误指出还恳请各位指出^_^文章来源地址https://www.toymoban.com/news/detail-853859.html
到了这里，关于动态规划之状压dp的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
