【C++动态规划 状态压缩】2597. 美丽子集的数目|2033

本文涉及知识点

C++动态规划

LeetCode2597. 美丽子集的数目

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
返回数组 nums 中 非空 且 美丽 的子集数目。
nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
示例 1：
输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。
示例 2：
输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。
提示：
1 <= nums.length <= 20
1 <= nums[i], k <= 1000

动态规划+状态压缩

动态规划的状态表示

dp[mask] 表示(1<<j)&mask的数字已经使用是否是完美子集。空间复杂度：O(2ⁿn)。

动态规划的填表顺序

mask从0到大

动态规划的转移方程

v[i]的如下位为1，其它为0:a，第i位。 b,第j位 abs(nums[j]-nums[i])==k。
!dp[mask]忽略。
if(v[i]&mask)则忽略i。
dp[mask|(1<<i)] = true
单个状态时间复杂度：O(n)，总时间复杂度：O(2ⁿn)

动态规划的初始化

dp[0]=true，其它全为false。

动态规划的返回值

dp中true的数量-1。

代码

核心代码

class Solution {public:int beautifulSubsets(vector<int>& nums, int k) {const int N = nums.size();const int MC = 1 << N;vector<int> v(N);for (int i = 0; i < N; i++) {v[i] = 1 << i;for (int j = 0; j < N; j++) {if (abs(nums[i] - nums[j]) == k) {v[i] |= (1 << j);}}}vector<bool> dp(MC);for (int i = 0; i < N; i++) {dp[1 << i] = true;}for (int i = 0; i < MC; i++) {if (!dp[i])continue;for (int j = 0; j < N; j++) {if (i & v[j])continue;dp[i | (1 << j)] = true;}}const int ans = count(dp.begin(), dp.end(), true);return ans;}};

单元测试

	int k;TEST_METHOD(TestMethod11){nums = { 2,4,6 },k=2;auto res = Solution().beautifulSubsets(nums, k);AssertEx(4, res);}TEST_METHOD(TestMethod12){nums = { 1 }, k = 1;auto res = Solution().beautifulSubsets(nums, k);AssertEx(1, res);}

优化

v[i] 改成v[i<<i]
枚举后续状态：
j1= i&-i j2 = i-j1
如果v[j1]&j2 则i是非法状态。否则dp[i] = dp[j2]

class Solution {public:int beautifulSubsets(vector<int>& nums, int k) {const int N = nums.size();const int MC = 1 << N;vector<int> v(MC);for (int i = 0; i < N; i++) {	for (int j = 0; j < N; j++) {if (abs(nums[i] - nums[j]) == k) {v[1<<i] |= (1 << j);}}}vector<bool> dp(MC);for (int i = 0; i < N; i++) {dp[1 << i] = true;}for (int i = 1; i < MC; i++) {const int j1 = i & -i;const int j2 = i - j1;if (j2 & v[j1])continue;dp[i] = (0==j2)||dp[j2];}const int ans = count(dp.begin(), dp.end(), true);return ans;}};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。