【状态机dp 状态压缩】2172. 数组的最大与和

本文涉及知识点

C++动态规划
位运算、状态压缩、枚举子集汇总

LeetCode2172. 数组的最大与和

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 * numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。
你需要把所有 n 个整数分到这些篮子中，且每个篮子至多有 2 个整数。一种分配方案的与和定义为每个数与它所在篮子编号的按位与运算结果之和。
比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。
请你返回将 nums 中所有数放入 numSlots 个篮子中的最大与和。
示例 1：
输入：nums = [1,2,3,4,5,6], numSlots = 3
输出：9
解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。
示例 2：
输入：nums = [1,3,10,4,7,1], numSlots = 9
输出：24
解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。
提示：
n == nums.length
1 <= numSlots <= 9
1 <= n <= 2 * numSlots
1 <= nums[i] <= 15

状态机动态规划

动态规划的状态

dp’[i][mask] 表示处理完前i个数组，篮子的状态为mask的最大与和。
令k=2 $\times$ (j-1) 第j个篮子的状态由k位和k+1位表示。两位都是0表示篮子为空；k位为1，k+1位0表示篮子有一个空位；k+1位为1，k位为0，忽略；两位都为1，表示篮子满了。
pre = dp’[i] dp=dp’[i+1]
用滚动数组的空间复杂度为：O(4^numSlots)
如果自己编码、解码空间复杂度可以降到O(3^numSlots)

动态规划的转移方程

枚举nums[i]放到第j个篮子。单状态转移的时间复杂度：O(1)。
总时间复杂度：O(n3^numSlotsm+n4^numSlots) $\approx$ 8 $\times$ 10⁶
注意：非法状态必须提前结束。

动态规划的初始值

pre[0]为0，其余全部为-1

动态规划的填表顺序

i从小到大

动态规划的返回值

max(pre)

代码

核心代码

class Solution {
public:int maximumANDSum(vector<int>& nums, int M) {const int N = nums.size();const int iMaskCnt = 1 << (2 * M);vector<int> pre(iMaskCnt, -1);pre[0] = 0;for (int i = 0; i < N; i++) {vector<int> dp(iMaskCnt, -1);for (int p = 0; p < iMaskCnt; p++) {if (-1 == pre[p]) { continue; }for (int j = 0; j < M; j++) {const int k = 2 * j;const bool b1 = p & (1 << k);const bool b2 = p & (1 << (k + 1));const int iAdd = (j + 1) & nums[i];if (b1 & b2) {	continue;	}if (b1) {const int nM = p | (1 << (k + 1));dp[nM] = max(dp[nM], pre[p] + iAdd);}else {const int nM = p | (1 << k);dp[nM] = max(dp[nM], pre[p] + iAdd);}}}pre.swap(dp);}return *std::max_element(pre.begin(), pre.end());}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,  double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> nums;int numSlots;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){nums = { 1, 2, 3, 4, 5, 6 }, numSlots = 3;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(9, res);}TEST_METHOD(TestMethod01){nums = { 1,3,10,4,7,1 }, numSlots = 9;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(24, res);}TEST_METHOD(TestMethod02){nums = {1 }, numSlots = 1;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(1, res);}TEST_METHOD(TestMethod03){nums = { 1 ,2}, numSlots = 1;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(1, res);}TEST_METHOD(TestMethod04){nums = { 1 ,2 }, numSlots = 2;auto res = Solution().maximumANDSum(nums, numSlots);AssertEx(3, res);}};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛