当前位置：首页 > article >正文

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

article 2025/1/31 3:15:34

本文涉及知识点

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;
			}
		};

扩展阅读

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