前言
楼主深刻感到自己动归的水平太差
痛定思痛，决定爆刷一些dp的题
因此在力扣上搜集了一些状压dp的题练习下，以本文作为记录
注意：本文不适合连一点状压dp概念的小白观看，且不会写过多文字作题解，一些尽在代码中
🔖思路与技巧
状压dp分为状压和dp两个关键点
一般状压dp的有些关键点，如n<=20，状态比较复杂等
当然并不是所有题的状压都是以二进制来进行状压，思路不能被局限
🔖碎碎念
状压dp的状压是一个难点，而dp又是一个难点
但很多状压题不一定是dp的形式展现的，比如很多可以用dfs搜索出来
但递推和搜索在很多状态转移的核心是一样的，因此本文有很多非dp的题目和解法
还有状压题目需要非常扎实的位运算基本功，还有位运算的运算优先级比较低，一定要注意套括号
题单
🏷️464. 我能赢吗
⭐典型博弈例题
题意与思路
给定1~n两个人分别取数，累计和先达到或超过total的选手获胜
非常经典的博弈问题，也是非常经典的dfs策略，借助后者dfs状态的返回，来判断当前是否获胜
博弈题通常用搜索的写法比递推的好写
Code
class Solution {
private:
int n;
int maxx;
vector<bool> vis;
bool dfs(int sum, int mask) {
// 该状态已访问过
if (vis[mask]) {
return false;
}
for (int i = 0; i < n; i += 1) {
if (mask & (1 << i)) {
continue;
}
int nexMask = mask | (1 << i);
int nexSum = sum + (i + 1);
if (nexSum >= maxx) {
return true;
}
// 下一轮对手失败，则当前获胜
if (!dfs(nexSum, nexMask)) {
return true;
}
}
vis[mask] = true;
return false;
}
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
n = maxChoosableInteger;
maxx = desiredTotal;
vis = vector<bool>(1 << n);
// sum == maxx的时候，因为n有奇偶的可能，因此不确定
if (n * (1 + n) / 2 < maxx) {
return false;
}
if (n >= maxx) {
return true;
}
return dfs(0, 0);
}
};🏷️526. 优美的排列
⭐线性匹配 (填数)
题意与思路
假设有从 1 到 n 的 n 个整数。
用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
- perm[i] 能够被 i 整除
- i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
本质就是那[1, n]到[1, n]的位置上进行配对
属于典型的线性匹配类
Code
二维dp刷表
一维dp查表
回溯刷表
// **二维dp**
// 刷表
class Solution {
public:
int countArrangement(int n) {
int MASK = 1 << n;
// 考虑第i个字母，状态为mask的可能
vector<vector<int>> dp(n + 1, vector<int>(MASK));
dp[0][0] = 1;
// 考虑填写的位置
for (int i = 1; i <= n; i += 1) {
// 往空位填这个i
for (int mask = 0; mask < MASK; mask += 1) {
// mask的位置
for (int nex = 0; nex < n; nex += 1) {
int prem = nex + 1;
int nexMask = mask | (1 << nex);
// 填过，continue
if (mask & (1 << nex)) {
continue;
}
// 没填过，且达到要求
if (i % prem == 0 || prem % i == 0) {
// 刷表
dp[i][nexMask] += dp[i - 1][mask];
}
}
}
}
return dp[n][MASK - 1];
}
};🏷️691. 贴纸拼词
⭐多位贡献
题意与思路
根据给定字符串数字，要求从中去最小个数的字符串(可重复，随意分割字符)，是否可以拼接成目标串
其实就是一个字符串可以贡献多个位，写搜索比较方便
Code
class Solution {
public:
int minStickers(vector<string>& stickers, string target) {
int n = target.size();
int MASK = 1 << n;
queue<int> q;
q.push(0);
unordered_map<int, bool> vis;
vis[0] = true;
int step = 0;
while (!q.empty()) {
int len = q.size();
while (len--) {
int cur = q.front();
q.pop();
if (cur == MASK - 1) {
return step;
}
for (string& s : stickers) {
int nex = cur;
for (char& ch : s) {
for (int i = 0; i < n; i++) {
// 字母相同，且该位置还未放字母
if ((target[i] == ch) && (!(nex & (1 << i)))) {
nex |= (1 << i);
break;
}
}
}
if (!vis[nex]) {
q.push(nex);
vis[nex] = true;
}
}
}
step++;
} // bfs
return -1;
}
};🏷️698. 划分为k个相等的子集
⭐排序贪心剪枝
题意与思路
如题名所示
第一次写的时候是开一个k大小的数组，分别回溯填入该数组中，记忆化就是记忆整个数组
但是借助一个规律就可以直接靠记录状压值来记忆化。
就是在不断累计中不断取模来处理单个组，当取模到0时说明一个组划分成功了。
Code
状压dp
dfs
// 状压dp
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(), 0);
int each = sum / k;
// 无法均分
if (each * k != sum) {
return false;
}
// 排序剪枝 从大到小可以让dfs更快的剪枝
sort(nums.begin(), nums.end(), greater<int>());
if (nums.front() > each) {
return false;
}
int n = nums.size();
int MASK = 1 << nums.size();
// 记录总和状态对应的余数
vector<int>dp = vector<int>(MASK);
// 记录访问
vector<bool> vis = vector<bool>(MASK);
vis[0] = true;
dp[0] = 0;
// 刷表法
for (int mask = 0; mask < MASK; mask += 1) {
if (!vis[mask]) {
continue;
}
for (int i = 0; i < n; i += 1) {
if (mask & (1 << i)) {
continue;
}
if (dp[mask] + nums[i] > each) {
break;
}
int nexMask = mask | (1 << i);
dp[nexMask] = (dp[mask] + nums[i]) % each;
vis[nexMask] = true;
}
}
return vis[MASK - 1] && dp[MASK - 1] == 0;
}
};🏷️847. 访问所有节点的最短路径
⭐状压+ 最短路
题意与思路
一个无向图，可以从任意点出发(可以多次访问)，求遍历完n个点的最短路
在一般的图论中确实是vis记录单个点
但是这题必然会碰到回溯的状态，因此是要 点和mask一起记录
但是我们访问的思路还是从单个点到单个点的状态进行状态转移
下面的bfs其实是一种刷表法的思路
其实本题是一种旅行商问题的变体
Code
状压dp
bfs
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
int MASK = 1 << n;
// Floyd 求最短路
int dis[n][n];
memset(dis, 0x3f, sizeof(dis));
for (int i = 0; i < n; i += 1) {
dis[i][i] = 0;
for (int j : graph[i]) {
// 无向边长度为1
dis[i][j] = dis[j][i] = 1;
}
}
for (int c = 0; c < n; c += 1) {
for (int from = 0; from < n; from += 1) {
for (int to = 0; to < n; to += 1) {
dis[from][to] = min(dis[from][to], dis[from][c] + dis[c][to]);
}
}
}
// 当前cur的点 处于mask的状态的最小值
int dp[n][1 << n];
memset(dp, 0x3f, sizeof(dp));
// 查表法
for (int mask = 1; mask < MASK; mask += 1) {
// 位运算一定要套括号
// 单个点，则表示起点，没有去过别的点，距离为0
if ((mask & (mask - 1)) == 0) {
// 后导0的个数
int cur = __builtin_ctz(mask);
dp[cur][mask] = 0;
continue;
}
// 多个点，表示经过了路径，则可以松弛
for (int cur = 0; cur < n; cur += 1) {
if ((mask & (1 << cur)) == 0) {
continue;
}
// 查表法
for (int pre = 0; pre < n; pre += 1) {
if ((pre != cur) && (mask & (1 << pre))) {
dp[cur][mask] = min(dp[cur][mask],
dp[pre][mask ^ (1 << cur)] + dis[cur][pre]);
}
}
}
}
// 查找每个点结尾的最小值
int ans = INT_MAX;
for (int i = 0; i < n; i += 1) {
ans = min(ans, dp[i][MASK - 1]);
}
return ans;
}
};☠️943. 最短超级串
☠️状压dp中的战斗机 / 没有写，留个坑
主要是本题还加入了各种字符串的处理实在太烦了
🏷️982. 按位与为零的三元组
⭐枚举二进制子集
题意与思路
在数组中任选三个元素使得三个元素的&为0(可以重复选)
本题的突破口在于数据范围
1 <= nums.length <= 10000 <= nums[i] < 2^16
显然这个1000很难突破，不可能写个O(n^3)的做法。
因此考虑0 <= nums[i] < 2^16
这正是这堆数能&出的范围
因此先统计两个数的所有&的情况，再考虑第三个数&上去
难点在于如何考虑第三个数
首先找出与num3&为0的补集，显然这个补集有很多
因此只要找个找个补集的最大值，再枚举所有子集即可
注意下方得补集没有考虑空集，因此需要特判
for (int set = mask; set > 0; set = (set - 1) & mask); /* 核心原理为不断消除低位的1 e.g: mask = 10101 10101 - 1 = 10100 10100 & 10101 = 10100 --- 10100 - 1 = 10011 10011 & 10101 = 10001 --- 10001 - 1 = 10000 10000 & 10101 = 10000 --- 10000 - 1 = 01111 01111 & 10101 = 00101 ... */
Code
class Solution {
public:
int countTriplets(vector<int>& nums) {
int n = nums.size();
// 这里根据题目的数据范围确定mask
int MASK = 1 << 16;
// 先统计二元组能构成的数字
vector<int> dp(MASK);
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
dp[nums[i] & nums[j]] += 1;
}
}
int ans = 0;
// 枚举第三个元素
for (int i = 0; i < n; i += 1) {
// 全1 ^ num = x
// x & num = 0
int mask = (MASK - 1) ^ nums[i];
// 枚举子集 (不包含空集)
// 这里每个 set & num = 0
for (int set = mask; set > 0; set = (set - 1) & mask) {
ans += dp[set];
}
// 0 & num = 0
ans += dp[0];
}
return ans;
}
};🏷️1125. 最小的必要团队
⭐01背包+寻路
题意与思路
有一个物品序列，每项有多个物品。给定一个目标集合，问获得目标集合的最小物品数量的集合
序列中的每个元素都是目标集合的元素
将序列的每个元素进行状态，再用01背包进行转移，松弛的时候记录一下路径。最后逆向寻路。
Code
class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
int n = people.size();
// 字符串转下表
unordered_map<string, int> hash;
for (int i = 0; i < req_skills.size(); i += 1) {
hash[req_skills[i]] = i;
}
// mask
const int MASK = 1 << (req_skills.size());
// 每个mask的状态所需要的集合大小，初始为全部
// 要求最小种类，则初始化最大
vector<int> dp(MASK, n);
vector<int> maskIdx(MASK);
vector<int> maskPath(MASK);
// 初始化0状态0个元素
dp[0] = 0;
for (int i = 0; i < n; i += 1) {
int mask = 0;
for (auto&& s : people[i]) {
mask |= 1 << hash[s];
}
for (int preMask = 0; preMask < MASK; preMask += 1) {
const int curMask = preMask | mask;
// 可以由前一个转过来
if (dp[preMask] + 1 < dp[curMask]) {
// 更新大小
dp[curMask] = dp[preMask] + 1;
// 记录前一个的mask
maskPath[curMask] = preMask;
// 在curMask下应该记录的是哪个idx
maskIdx[curMask] = i;
}
}
}
vector<int> ans;
int mask = MASK - 1;
while (mask) {
ans.push_back(maskIdx[mask]);
mask = maskPath[mask];
}
return ans;
}
};🏷️1255. 得分最高的单词集合
⭐纯枚举所有状态
题意与思路
给出一堆字符和价值量，要求只能拼成目标单词
求最大的价值
初看一下又类似背包选与不选的限制
容易往常见的线性递推的状压dp的方向思考，但一思考就很复杂
但是跳出递推的思维陷阱，就像二进制枚举一样，纯枚举状态在暴力求解即可
Code
class Solution {
private:
inline static const int M = 26;
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> cntSum(M);
for (char ch : letters) {
cntSum[ch - 'a'] += 1;
}
int n = words.size();
int MASK_MAX = 1 << n;
vector<int> dp(MASK_MAX);
int ans = 0;
for (int mask = 0; mask < MASK_MAX; mask += 1) {
// 统计mask这个子集的状态和
vector<int> cntMask(M);
for (int i = 0; i < n; i += 1) {
// 过滤掉不在mask中的
if ((mask & (1 << i)) == 0) {
continue;
}
// 统计在mask中的
for (char ch : words[i]) {
cntMask[ch - 'a'] += 1;
}
}
// 统计这个子集的大小
int sum = 0;
bool flag = true;
for (int i = 0; i < M && flag; i += 1) {
flag &= cntMask[i] <= cntSum[i];
sum += score[i] * cntMask[i];
}
flag && (ans = max(ans, sum));
}
return ans;
}
};🏷️1349. 参加考试的最大学生数
⭐轮廓线dp
题意与思路
给定一个n*m <= 64的矩阵表示教室的座位，规定每个位置若坐人则受到左右和上层斜左右的限制，问做多能做多少人
这是一道轮廓线dp的题，这类题个人做的不多，不是很熟
本题有两个限制，上层斜左右，本层左右。其实一层一层的判断思维还是比较好理解的(看题就行了)，但具体实现的编码比较难
下方代码cv的官方题解，这份题解的各种位运算用的溜的飞起！
可以自行搜索一道比较经典的轮廓线dp ：Mondriaan's Dream
Code
有朝一日补上递推的写法
class Solution {
private:
int dp[8][1 << 8];
int row, col;
vector<int> maskState;
// 上一层的状态
// dp的层数
// 状压个数
// 用curMask去刷下一层
int dfs(int curMask, int idx) {
// 记忆化
if (dp[idx][curMask] != -1) {
return dp[idx][curMask];
}
const int MASK = 1 << col;
int ans = 0;
// 枚举curMask的所有可能
for (int mask = 0; mask < MASK; mask += 1) {
// - 由于保证了dfs与上一层关系正确，因此只考虑当前层的check
// - 这两个写法都很巧妙
// '#'位置不能
// 相邻左右两边不能
if ((mask & (~curMask)) || (mask & (mask << 1))) {
continue;
}
// 该mask有多少位置坐下了
int cur = 0;
for (int i = 0; i < col; i += 1) {
if (mask & (1 << i)) {
cur += 1;
}
}
// 最后一行不用转移，直接松弛
if (idx + 1 == row) {
ans = max(ans, cur);
} else {
// 获取下一层的实际状态
int nexMask = maskState[idx + 1];
// 通过左右各移一位，来与下一层的&
// 保证nex的上层左右对角不同
nexMask &= ~(mask << 1);
nexMask &= ~(mask >> 1);
ans = max(ans, cur + dfs(nexMask, idx + 1));
}
}
return dp[idx][curMask] = ans;
}
public:
int maxStudents(vector<vector<char>>& seats) {
memset(dp, -1, sizeof(dp));
this->row = seats.size();
this->col = seats.front().size();
// 转化为二进制矩阵
for (vector<char> & arr : seats) {
int mask = 0;
for (int bit = 0; bit < col; bit += 1) {
mask <<= 1;
mask |= (arr[bit] == '.');
}
maskState.push_back(mask);
}
// 从第一层往下dp
return dfs(maskState.front(), 0);
}
};🏷️1494. 并行课程 II
⭐拓扑排序转为状压转移 + 枚举子集
题意与思路
规定一次只能访问k个入度为1的点。求最终访问完要多少次。
如果是基于回溯考虑所有状态的话复杂度会非常非常大。
换一种思路，用状压表示已经访问过的点。
先预处理所有单次取k个的可行状态
查表法 枚举当前mask的子集，从子集中找正好取k个预处理的状态来松弛
Code
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
const int MASK = 1 << n;
// 统计第i门课程需要的所有前驱
vector<int> oneCoursePre(n);
for (auto&& course : relations) {
// [1, n] -> [0, n-1]
int from = course[0] - 1;
int to = course[1] - 1;
oneCoursePre[to] |= (1 << from);
}
// mask 状态需要的前驱
vector<int> maskPre(MASK);
// mask 状态是否合法
vector<bool> valid(MASK); // 有人用std::vector<bool> 超时，这里再次测试一下
for (int mask = 0; mask < MASK; mask += 1) {
// 找出在k步以内的状态
if (__builtin_popcount(mask) > k) {
continue;
}
// 累计这个mask下每门课程的所有前驱
for (int i = 0; i < n; i += 1) {
if (mask & (1 << i)) {
maskPre[mask] |= oneCoursePre[i];
}
}
// 这个mask不能构成自回路
valid[mask] = (mask & maskPre[mask]) == 0;
}
// 状压dp dp[mask]状态mask下需要的总步数
vector<int> dp(MASK, INT_MAX / 2);
dp[0] = 0;
// 已经选了mask状态的课
for (int mask = 0; mask < MASK; mask += 1) {
// 枚举所有子集
for (int subMask = mask; subMask > 0; subMask = (subMask - 1) & mask) {
// 1. 子集合法
// 2. 子集的前驱课也都是mask的前驱课
if (valid[subMask]
&& (mask & maskPre[subMask]) == maskPre[subMask]) {
// 查表法
dp[mask] = min(dp[mask], dp[mask ^ subMask] + 1);
}
}
}
return dp[MASK - 1];
}
};🏷️1595. 连通两组点的最小成本
⭐二分图匹配 -> 考虑一次线性去匹配另一次的mask
题意与思路
二分图匹配，要求两端的点都有匹配(可以不止一个)，最终成本最小。
两端都是mask的话复杂度非常高。
考虑一侧线性遍历，另一次mask枚举全状态。
但是不是直接从mask1道mask2。匹配是两个点的匹配从mask中单独取出单个点进行与左侧匹配。
然后三种情况进行转移。
- 从没有左侧的i 尝试松弛
- 从没有右侧的k 尝试松弛
- 左右都没有这两个点 尝试松弛
Code
class Solution {
public:
int connectTwoGroups(vector<vector<int>>& cost) {
const int n = cost.size(), m = cost[0].size();
const int MASK = 1 << m;
// dp[i][mask]
// 对应左侧第i行对应，右侧链接的mask状态的value
int dp[n + 1][MASK];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
// 考虑左侧的第i行
for (int i = 1; i <= n ; i += 1) {
// 连接所需要的贡献
auto& linkVal = cost[i - 1];
// 枚举所有的mask状态
for (int mask = 0; mask < MASK; mask += 1) {
for (int k = 0; k < m; k += 1) {
const int offset = (1 << k);
// 这个mask没有右侧的这个right
if ((mask & offset) == 0) {
continue;
}
/// 到这里dp[i][mask]
/// 表示左侧已经有i这个点
/// 右侧在mask中已经有k这个点
// 从没有左侧的i 尝试松弛
dp[i][mask] = min(dp[i][mask], dp[i - 1][mask] + linkVal[k]);
// 从没有右侧的k 尝试松弛
dp[i][mask] = min(dp[i][mask], dp[i][mask ^ offset] + linkVal[k]);
// 左右都没有这两个点 尝试松弛
dp[i][mask] = min(dp[i][mask], dp[i - 1][mask ^ offset] + linkVal[k]);
}
}
} // for left line
return dp[n][MASK - 1];
}
};🏷️1659. 最大化网格幸福感
⭐轮廓线dp + 三进制压缩
题意与思路
在一个矩阵中放两种点，每种点有一个原始值。且放置相近后还有其余贡献。求可获得的最值。(不用放完)
看到n*m矩阵，相邻的贡献，就基本确定是轮廓线dp了
Code
cv官解。楼主个人对轮廓线dp的能力还未掌握。
class Solution {
private:
static constexpr int T = 243, N = 5, M = 6;
// 0 什么都不放
// 1 放in
// 2 放ex
// 造成的格外贡献
static constexpr int score[3][3] = {
{0, 0, 0},
{0, -60, -10},
{0, -10, 40}
};
// 行，列，总量
int col, row;
// 3^i 的power
int power3[N];
// 轮廓线dp
// dp[pos][mask][incnt][excnt]
// 考虑到pos的位置
// 状态为mask的时候
// 还需要放in cnt个
// 还需要放ex cnt个
int dp[N * M][T][M + 1][M + 1];
public:
int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
// 列
this->col = n;
// 行
this->row = m;
power3[0] = 1;
for (int i = 1; i < n; i += 1) {
power3[i] = power3[i - 1] * 3;
}
// 记忆化搜索
memset(dp, -1, sizeof(dp));
// 从0位置开始搜索，零位置的mask是0
return dfs(0, 0, introvertsCount, extrovertsCount);
}
int dfs(int pos, int mask, int inCnt, int exCnt) {
// 搜索完，或者没点可以放了
if (pos == col * row || (inCnt == 0 && exCnt == 0)) {
return 0;
}
// &ans
int& res = dp[pos][mask][inCnt][exCnt];
// 记忆化
if (res != -1) {
return res;
}
res = 0;
int up = mask / power3[col - 1];
int left = mask % 3;
// 轮廓线dp第一列特判
if (pos % col == 0) {
left = 0;
}
// 三进制压缩
// i = 0 什么都不放
// i = 1 放in
// i = 2 放ex
for (int i = 0; i < 3; i += 1) {
if ((i == 1 && inCnt == 0) || (i == 2 && exCnt == 0)) {
continue;
}
int nexMask = mask % power3[col - 1] * 3 + i;
int scoreSum = dfs(pos + 1, nexMask, inCnt - (i == 1), exCnt - (i == 2))
+ score[up][i]
+ score[left][i];
if (i == 1) {
scoreSum += 120;
} else if (i == 2) {
scoreSum += 40;
}
res = max(res, scoreSum);
}
return res;
}
};🏷️1681. 最小不兼容性
⭐预处理子状态 + 枚举子集查表
题意与思路
在数组中每次k个一组，每组有一份贡献。选取nums.size()/k组，求最小花费。
和1494. 并行课程 II 很像，单次有规定大小的处理量，先预处理好。再枚举mask的子集进行转移。
而这题再枚举mask的时候是需要计算补集的。
Code
class Solution {
private:
inline static const int INF = 0x3f3f3f3f;
public:
int minimumIncompatibility(vector<int>& nums, int k) {
const int n = nums.size();
const int MASK = 1 << n;
const int each = n / k;
// 预处理每个确定大小的合法子集的贡献值
vector<int> eachVal(MASK, -1);
for (int mask = 0; mask < MASK; mask += 1) {
// 合法子集需要正好是each个
if (__builtin_popcount(mask) != each) {
continue;
}
set<int> vis;
for (int i = 0; i < n; i += 1) {
if (mask & (1 << i)) {
vis.insert(nums[i]);
}
}
// 需要保证每个元素的不同
if (vis.size() == each) {
eachVal[mask] = *vis.rbegin() - *vis.begin();
}
}
vector<int> dp(MASK, INF);
dp[0] = 0;
// 刷表法，从已知状态去刷未知状态
for (int mask = 0; mask < MASK; mask += 1) {
if (dp[mask] == INF) {
continue;
}
// 从全集获取当前mask的补集
int complement = ((1 << n) - 1) ^ mask;
// 枚举补集的所有子集
for (int sub = complement; sub > 0; sub = (sub - 1) & complement) {
// 这个子集是合法有值的
if (eachVal[sub] != -1) {
// 刷表法
dp[mask | sub] = min(dp[mask | sub], dp[mask] + eachVal[sub]);
}
}
}
return dp[MASK - 1] == INF ? -1 : dp[MASK - 1];
}
};🏷️1723. 完成所有工作的最短时间
与2305. 公平分发饼干 完全一致
🏷️1799. N 次操作后的最大分数和
⭐线性匹配 + 偶数配对
题意与思路
有n个数字(n为偶数)，每次取两个数删除，并得到贡献(含一个取次系数)，求最大价值
比较特殊的一道线性匹配题，需要偶数个1才能搜索出两个数进行匹配
注意a,b和b,a是一样的贡献
本题用刷表法需要多加判断才行
Code
class Solution {
public:
int maxScore(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> val(n, vector<int>(n));
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
val[i][j] = __gcd(nums[i], nums[j]);
}
}
int MASK = 1 << n;
vector<int> dp(MASK);
for (int mask = 0; mask < MASK; mask += 1) {
int cnt = __builtin_popcount(mask);
// 奇数个则不匹配
if (cnt & 1) {
continue;
}
// 化为组数，即题意中的操作数
cnt /= 2;
// 双循环搜索两个数字
for (int first = 0; first < n; first += 1) {
// 保证有第一个该数字
if ((mask & (1 << first)) == 0) {
continue;
}
for (int second = first + 1; second < n; second += 1) {
// 保证有第二个数字
if ((mask & (1 << second)) == 0) {
continue;
}
// 查表法 前一个状态+题意的贡献方程
int preMask = mask ^ (1 << first) ^ (1 << second);
dp[mask] = max(dp[mask], dp[preMask] + cnt * val[first][second]);
}
}
}
return dp[MASK - 1];
}
};🏷️1879. 两个数组最小的异或值之和
⭐线性匹配 + 典型题意迷惑
题意与思路
有 nums1 和 nums2两个数组，要求每个对应位置相互^并求和，求最总答案最小的
其中num1确定，nums2可以任意排序
典型的说可以排序(即有顺序要求)。但实际思考，其实有没有顺序没有关系，就是要考虑所有数字配对的情况
典型的迷惑，也是典型的状态dp
Code
class Solution {
public:
// num1确定 num2排序
// num2确定 num1排序
// 性质是一样的
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
const int MASK = 1 << n;
vector<int> dp(MASK, 0x3f3f3f3f);
dp[0] = 0;
for (int mask = 1; mask < MASK; mask += 1) {
int cnt = __builtin_popcount(mask);
for (int i = 0; i < n; i += 1) {
// 不存在
if ((mask & (1 << i)) == 0) {
continue;
}
// 查表
int preMask = mask ^ (1 << i);
dp[mask] = min(dp[mask], dp[preMask] + (nums1[cnt - 1] ^ nums2[i]));
}
}
return dp[MASK - 1];
}
};🏷️1947. 最大兼容性评分和
⭐线性匹配
题意与思路
每个学生可以从不同的老师那获得一个得分，一个老师对应一个学生，求一种方案使得总价值最大
典型的线性匹配问题。仔细思考会发现起始无论从学生找老师，还是老师找学生，似乎与顺序是无关的。
因此可以借助二进制中1的个数表示处理了第几个学生。
借助前面的状态来松弛取max
Code
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int n = students.size();
// 枚举所有的情况 学生*老师
vector<vector<int>> val(n, vector<int>(n));
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
for (int k = 0; k < students[i].size(); k += 1) {
val[i][j] += (students[i][k] == mentors[j][k]);
}
}
}
// 状压dp
// 由于学生和老师一一对应
// dp[mask:1]表示这个位置的老师分配了
// count(mask:1)表示多少个配对
vector<int> dp(1 << n);
// 刷表法 全1状态下就没必要刷了(当然写了也不会错) 但是查表法就需要注意边界问题了
for (int mask = 0; mask < (1 << n) - 1; mask += 1) {
// 学生配对个数
int i = __builtin_popcount(mask);
// 遍历老师供提供
for (int j = 0; j < n; j += 1) {
// 这个老师还未被分配
if ((mask & (1 << j)) == 0) {
int k = mask | (1 << j);
dp[k] = max(dp[k], dp[mask] + val[i][j]);
}
}
}
return dp[(1 << n) - 1];
}
};🏷️1994. 好子集的数目
⭐子集状态转移
题意与思路
统计子数组，该子数组的元素乘积是一个分解质因数后，每个质因数只有一个的数字。求子数组个数。
核心内容在于质数，由于数字大小限定在30内，而30内的质数个数只有10个，正好在状压的可行范围内。
每个数字会提供一定的质因数，判断是否只出现一次后并获得一个贡献子集
用该子集来进行转移
注意：1这个数字可以随意产生贡献，要单独处理
Code
官方解法
以前写的一个看不懂的屎山
class Solution {
private:
// 30以内的质数
const vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
const int maxx = 30;
const int mod = 1e9 + 7;
public:
int numberOfGoodSubsets(vector<int>& nums) {
// 技术与分组
vector<long long> cnt(maxx + 1);
for (int& num : nums) {
cnt[num] += 1;
}
const int n = primes.size();
const int MASK = 1 << n;
// mask状态下(质数)的大小次数
vector<long long> dp(MASK);
// 统计原数组中1的贡献
// 一般来说是统计到dp[1]中的，但与定义不符合
// 定义为取质数的状态
// 但是这里作为初始状态的0来提供初值
dp[0] = 1;
for (int i = 0; i < cnt[1]; i += 1) {
dp[0] = dp[0] * 2 % mod;
}
// 考虑每个数字可能产生的贡献
for (int i = 2; i <= maxx; i += 1) {
// 一个都没有，无法产生贡献
if (cnt[i] == 0) {
continue;
}
// 判断该数字是否是由不同的单个质数组成
int subSet = 0;
int num = i;
bool check = true;
for (int j = 0; j < n; j += 1) {
// 出现两次及以上false
// 出现一次 记录子集合
if (num % (primes[j] * primes[j]) == 0) {
check = false;
break;
}
if (num % primes[j] == 0) {
subSet |= 1 << j;
}
}
if (check == false) {
continue;
}
// 类似于01背包的状态压缩，逆序便利
for (int mask = MASK - 1; mask > 0; mask += -1) {
// 正好是子集，则查表
if ((mask & subSet) == subSet) {
dp[mask] = (dp[mask] + 1LL * dp[mask ^ subSet] * cnt[i]) % mod;
}
}
}
long long ans= 0;
for (int mask = 1; mask < MASK; mask += 1) {
ans = (ans + dp[mask]) % mod;
}
return ans;
}
};🏷️2002. 两个回文子序列长度的最大乘积
⭐两个互斥子集
题意与思路
给出一个字符串。选定两个序列，求两个序列的长度乘积。
序列要求：
- 是回文串
- 两个序列互斥
观察到长度为2 <= s.length <= 12。可以直接状压枚举所有情况。
然后两个序列的话，分别跑一个双循环。数据量为pow(2, n) ^ 2 ≈ 1.7 * 10^8。2秒内勉强能跑完。加上一些减枝的话可以再快点。当然也可以预处理所有能构成回文的先mask。
关于如何判断子序列的回文。其实和普通串判断回文一样，只要掠过不取的点即可。
Code
class Solution {
private:
string s;
// 判断根据二进制判断是否回文
// 设置左右两个双指针，同时向中间靠近
// 力扣平台（编译器）中int为4bytes,32bits大小
bool check(const int mask) {
int left = 0;
int right = sizeof(int) * 8 - 1;
while (left < right) {
// 左边的低bit向高处搜索
while (((mask >> left) & 1) == 0) {
left += 1;
}
// 右边的高bit向地处搜索
while (((mask >> right) & 1) == 0) {
right += -1;
}
if (s[left] != s[right]) {
break;
} else {
left += 1;
right += -1;
}
}
return left >= right;
}
public:
int maxProduct(string s) {
this->s = s;
const int n = s.size();
const int Mask = 1 << n;
// 最低是两个单字符的序列
int ans = 1;
// 二进制状态，枚举所有所有情况
for (int mask1 = 1; mask1 < Mask; mask1 += 1) {
// 第1个子序列是回文
if (check(mask1) == false) {
continue;
}
for (int mask2 = mask1 + 1; mask2 < Mask; mask2 += 1) {
// 第2个子序列是回文
// 并且两个序列互斥
if (check(mask2) == false || (mask1 & mask2)) {
continue;
}
// 此时获得两个合法且互斥的mask
// 统计二进制中1的个数
int len1 = __builtin_popcount(mask1);
int len2 = __builtin_popcount(mask2);
ans = max(ans, len1 * len2);
}
}
return ans;
}
};🏷️2172. 数组的最大与和
⭐线性匹配 三进制状压
题意与思路
每个篮子放入数字后有价值，求价值最大，但是每个篮子可以放两个数字
和1947. 最大兼容性评分和 一样属于线性匹配问题
思路1：直接再复制一份篮子，假设每个篮子放一个，可以用二进制状压dp
思路2：直接三进制状压
Code
二进制状压
三进制状压
class Solution {
public:
int maximumANDSum(vector<int>& nums, int numSlots) {
int n = nums.size();
// 每个篮子可以放两个，则直接延伸一倍
int m = numSlots * 2;
int ans = 0;
// m个篮子，第i个位置是否存放物品
vector<int> dp(1 << m);
// 查表法从mask=1开始
for (int mask = 1; mask < (1 << m); mask += 1) {
// 统计有多少个位置放了
int cnt = __builtin_popcount(mask);
// 若超过了物品数，则过滤
if (cnt > n) {
continue;
}
// 物品的顺序是无所谓的信息
// 因此直接用1的个数cnt来表示利用第几个物品
// 考虑m大小的每个位置
for (int bit = 0; bit < m; bit += 1) {
// 该位开始被占用，则查表
if (mask & (1 << bit)) {
// 取消掉第bit位，并加上权值(类似背包dp)
// 注意位运算的优先级
// 题意:这个m长度是两倍的，因此m/2
dp[mask] = max(dp[mask],
dp[mask ^ (1 << bit)] +
((nums[cnt - 1]) & (bit / 2 + 1)));
}
}
ans = max(ans, dp[mask]);
}
return ans;
}
};🏷️2305. 公平分发饼干
⭐枚举子集 + 轮次迭代
题意与思路
现在有一组数据与k个人。所有数据都唯一的分配给一个人。
分配时尽量让每个人都数值最大化，最终所有方案的最小化。
一眼看到最终的求值方案，可能会一下子往二分的角度考虑。
其实本题可以二分，但是具体的check写的比较苦难，而且好很多辅助和技巧。
这里主要讲解状压dp的做法。看到这个数据量，就知道这是可能可以状压的信号。
根据题意每个人最终是获取全集的一个子集。这又是一个枚举子集的信号。
这里定义dp[i][mask]表示考虑了i个人，在mask状态下的答案。
考虑到每个人时可以用查表法，从上一轮的状态进行转移，具体做法和思路请看代码注释。
这种写法本质是一种多轮的迭代的效果，将前面[1, i -1]作为一个整体的状态给我门迭代。
因此可以将二维dp改成一维dp，这就是一些dp基本功问题了，此处暂时不给出一维的code。
Code
class Solution {
public:
int distributeCookies(vector<int>& cookies, int k) {
const int n = cookies.size();
const int Mask = 1 << n;
// 预处理每个mask所贡献的值
int val[Mask];
memset(val, 0, sizeof(val));
for (int mask = 0; mask < Mask; mask += 1) {
for (int j = 0; j < n; j += 1) {
if (mask & (1 << j)) {
val[mask] += cookies[j];
}
}
}
// dp[i][mask]
// 考虑了i个孩子时，分配mask状态的值
// 这里的意思是前[1, i-1]个孩子已经考虑完了
int dp[k + 1][Mask];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= k ; i += 1) {
for (int mask = 0; mask < Mask; mask += 1) {
// 枚举子集（不包含空集）
// 将子集sub施加到当前的第i个孩子身上
for (int sub = mask; sub; sub = (sub - 1) & mask) {
// 注意这里的松弛条件
// 首先题意是求最小值
// 因此最外层是min也和上面的dp初始化为INF对应
// 而内部的另一个松弛量
// 考虑当前分配到的一个独立集合sub的贡献
// 考虑去掉这个sub前一轮已经记录好mask的贡献
// 所能维护的最大值
dp[i][mask] = min(dp[i][mask], max(dp[i - 1][mask ^ sub], val[sub]));
}
}
}
return dp[k][Mask - 1];
}
};END
评论 (12)
