状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串 01 数字（二进制数）来表示各个点的状态。这就要求使用状态压缩的对象的点的状态必须只有两种，0 或 1 ；当然如果有三种状态用三进制来表示也未尝不可。
状态压缩DP：顾名思义，就是用状态压缩实现DP。
状态压缩DP的两个基本特征：
- 问题的数据规模特别小，2 的阶乘次可以通过。
- 题目通常都是选与不选两种选择，可以使用二进制串表示。
| 操作 | 解释 |
|---|---|
| A |= 1 << c | 将c插入集合A |
| A &= ~(1 << c) | 将c从集合A中移除（A中不一定要有c） |
| A ^= 1<< c | 将c从集合A中移除（A中要有c） |
| A & (-A) | 取集合A中的最小元，即最靠右的1 （lowbit） |
| A = 0 | 集合A置空 |
| A | B | 取集合A、B的并集 |
| A & B | 取集合A、B的交集 |
| A = (1 << len) - 1 | 集合A设为全集（长度为len） |
| (A & B) == B | B是A的子集 |
| (A >> k) & 1 | 集合A第k位的状态（0或1） |
| A &= (A - 1) | 将集合A最右边的1置0 |
-
链接：https://leetcode.cn/problems/beautiful-arrangement/
-
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一 ，该数组就是一个 优美的排列 ：
perm[i] 能够被 i 整除
i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。 -
解题思路：定义dp[i] [state]为考虑前 i 个数，且当前选择方案为 state 的所有方案数量，可以推出状态转移方程：
-
d p [ i ] [ s t a t e ] = ∑ k = 1 n d p [ i − 1 ] [ s t a t e & ! ( 1 < < ( k − 1 ) ) ] (1) dp[i][state] = sum_{k=1}^{n}dp[i - 1][state&!(1 << (k - 1))] tag{1} dp[i][state]=k=1∑ndp[i−1][state&!(1<<(k−1))](1)
-
代码：
class Solution { public: int countArrangement(int n) { int mask = 1 << n; // 最大状态数量 //int[][] dp = new int[n + 1][mask]; vectordp[n + 1]; for (vector v : dp) v.resize(mask); dp[0][0] = 1; // 枚举每个数字 for (int i = 1; i <= n; i++) { // 枚举所有的状态 for (int state = 0; state < mask; state++) { // 枚举位置 i（最后一位）选的数值是 k for (int k = 1; k <= n; k++) { // 首先 k 在 state 中必须是 1，即该状态未被枚举过 if (((state >> (k - 1)) & 1) == 0) continue; // 数值 k 和位置 i 之间满足任一整除关系 if (k % i != 0 && i % k != 0) continue; // state & (~(1 << (k - 1))) 代表将 state 中数值 k 的位置置零 dp[i][state] += dp[i - 1][state & (~(1 << (k - 1)))]; } } } return dp[n][mask - 1]; } }
链接：https://leetcode.cn/problems/stickers-to-spell-word/
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
- n == stickers.length
- 1 <= n <= 50
- 1 <= stickers[i].length <= 10
- 1 <= target.length <= 15
- stickers[i] 和 target 由小写英文单词组成
解题思路：定义 dp[i] 表示在 i 状态时使用的最少贴纸数量
代码：
class Solution {
public:
int minStickers(vector& stickers, string target) {
int maxLen = 16;
int n = target.size();
int m = 1 << n;// 状态数量
int dp[m];// dp[i] 表示在i状态时使用的最小贴纸数量
for (int i = 0; i < m; ++i) {// 初始化
dp[i] = i == 0 ? 0 : maxLen;// target的每个位置都为0的时候，使用贴纸的数量为0
}
for (int j = 0; j < m; ++j) {// 对所有状态进行遍历
if (dp[j] == maxLen) continue;
for (string s : stickers) {// 每种状态下对每个单词遍历
int cur = j;// 当前贴纸状态
for (char c : s) {// 分别取s单词中的所有字母
for (int k = 0; k < n; ++k) {
// target的第k位为该字母，且该位置上没有贴纸
if (target[k] == c && ((cur >> k) & 1) == 0) {
cur |= (1 << k);// 将该位置贴上贴纸
break;
}
}
}// 贴完了一张贴纸
// cur状态的值：取j状态下贴一张贴纸以及cur状态所需贴纸的最小值
dp[cur] = min(dp[cur], dp[j] + 1);
}
}
return dp[m - 1] >= maxLen ? -1 : dp[m - 1];
}
};
我能赢吗
-
链接：https://leetcode.cn/problems/can-i-win/
-
在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现最佳 。
- 1 <= maxChoosableInteger <= 20
- 0 <= desiredTotal <= 300
-
解题思路：mp[i] 表示在 i 状态下的三种情况：-1 表示还未被遍历，0 表示该状态不能获胜，1 表示该状态能获胜。
-
代码：
class Solution { public: bool canIWin(int maxChoosableInteger, int desiredTotal) { if ((maxChoosableInteger + 1) * maxChoosableInteger < desiredTotal) return false; int mp[1 << maxChoosableInteger]; memset(mp, -1, sizeof(int) * (1 << maxChoosableInteger)); return dfs(maxChoosableInteger, desiredTotal, 0, 0, mp); } bool dfs(int maxChoosableInteger, int desiredTotal, int visited, int curNumber, int* mp) { // 该状态已经遍历过了 if (mp[visited] != -1) return mp[visited]; for (int i = 0; i < maxChoosableInteger; ++i) { // 当前位数已经选过，直接跳过 if (((visited >> i) & 1) == 1) continue; // 该状态下满足要求 if (curNumber + i + 1 >= desiredTotal) { mp[visited] = 1; return mp[visited]; } else { // 对手输 if (!dfs(maxChoosableInteger, desiredTotal, visited | (1 << i), curNumber + i + 1, mp)) { mp[visited] = 1; return mp[visited]; } } } // 当前状态不能获胜 if (mp[visited] == -1) mp[visited] = 0; return mp[visited]; } };
