【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和

本文涉及知识点

动态规划 区间dp 位运算

LeetCode3117. 划分数组得到最小的值之和

给你两个数组 nums 和 andValues，长度分别为 n 和 m。
数组的 值 等于该数组的 最后一个 元素。
你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & … & nums[ri] == andValues[i] ，其中 & 表示按位AND运算符。
返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。
示例 1：
输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]
输出： 12
解释：
唯一可能的划分方法为：
[1,4] 因为 1 & 4 == 0
[3] 因为单元素子数组的按位 AND 结果就是该元素本身
[3] 因为单元素子数组的按位 AND 结果就是该元素本身
[2] 因为单元素子数组的按位 AND 结果就是该元素本身
这些子数组的值之和为 4 + 3 + 3 + 2 = 12
示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

[[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17
[[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
[[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
子数组值之和的最小可能值为 17

示例 3：

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回 -1。
提示：
1 <= n == nums.length <= 10⁴
1 <= m == andValues.length <= min(n, 10)
1 <= nums[i] < 10⁵
0 <= andValues[j] < 10⁵

动态规划的位运算

f(i,j) = $\&{=}_{x:i}^j$
vNext[cur] 记录符合以下条件之一的next：
一，next-1 < cur。
二，f(i,next) $\ne$ f(i,next-1)。
iBitCnt = log(max(nums[i]) $\approx$ 22 ，显然next的数量不会超过iBitCnt。
如果f(i,j)发生变化，至少一个二进制1变成0。

动态规划

动态规划的状态表示

dp[len][cur] 表示将nums[0…cur]划分为len个区间的最小和。
空间复杂度：O(nm)

动态规划的转移方程

r个区间向r+1个区间转移时：
如果f(cur,next) 等于 andValues[r-1]则:
MinSelf(dp[r+1][x],dp[r][cur-1]+nums[x]) x$\in [next,next的下一个值)这样值设置的时间复杂度是：$$O(m\times n\times iBitCnt\times n)$ ，超时了。
只更新：x = next，其它的用二种方式更新：
如果 (nums[cur]& andValues[r-1]) = andValues[r-1]
则MinSelf(dp[r][cur],dp[r][cur-1])
时间复杂度：$$O(m\times n\times iBitCnt)$

动态规划的初始值

枚举第一个区间

动态规范的返回值

dp.back().back()

动态规划的填表顺序

len 从1到m_r-1。
cur从1到m_c-1

代码

核心代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft,(ELE) other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
		const int iBitCnt = 22;
		m_r = andValues.size();
		m_c = nums.size();
		const int iMax = (1 << iBitCnt) - 1;
		vector<vector<int>> dp(m_r+1,vector<int>(m_c, m_iNotMay));
		int iAnd = iMax;
		for (int i = 0; i < m_c; i++) {
			iAnd &= nums[i];
			if (iAnd == andValues[0]) {
				dp[1][i] = nums[i];
			}
		}
		vector<set<int>> vNext(m_c);
		{
			vector<int> next(iBitCnt, m_c);
			for (int i = nums.size() - 1; i >= 0; i--) {
				vNext[i] = set<int>(next.begin(), next.end());
				vNext[i].emplace(i);
				vNext[i].erase(m_c);
				for (int bit = 0; bit < iBitCnt; bit++)
				{
					bool b = (1 << bit) & nums[i];
					if (!b) {
						next[bit] = i;
					}
				}
			}
		}
		for (int r = 1; r < m_r; r++)
		{
			for (int cur = 1; cur < m_c; cur++)
			{
				int iAdd = iMax;
				for (const auto& next : vNext[cur]) {
					iAdd &= nums[next];
					if (andValues[r] == iAdd) {
						MinSelf(&dp[r + 1][next], dp[r][cur - 1] + nums[next]);
					}
				}
				if ((andValues[r - 1] & nums[cur]) == andValues[r - 1]) {
					MinSelf(&dp[r][cur], dp[r][cur - 1]+nums[cur]-nums[cur-1]);
				}				
			}			
		}
		{
			int r = m_r;
			for (int cur = 1; cur < m_c; cur++)
			{				
				if ((andValues[r - 1] & nums[cur]) == andValues[r - 1]) {
					MinSelf(&dp[r][cur], dp[r][cur - 1] + nums[cur] - nums[cur - 1]);
				}
			}
		}
		const int iRet = dp.back().back();
		return (iRet >= 1'000'000) ? -1 : iRet;
	}
	int m_r,m_c;
	const int m_iNotMay = 1'000'000'000;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{

	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int>  nums, andValues;
	int k;

	{
		Solution sln;
		nums = { 1, 9, 8, 8 }, andValues = { 1,8 };
		auto res = sln.minimumValueSum(nums, andValues);
		Assert(9, res);
	}
	{
		Solution sln;
		nums = { 1, 3, 2, 4, 7, 5, 3 }, andValues = { 0, 5, 3 };
		auto res = sln.minimumValueSum(nums, andValues);
		Assert(12, res);
	}
	{
		Solution sln;
		nums = { 1, 4, 3, 3, 2 }, andValues = { 0, 3, 3, 2 };
		auto res = sln.minimumValueSum(nums, andValues);
		Assert(12, res);
	}

	//vector<int>  nums = { 3,6,9 };
	//int k;
	//
	//{
	//	Solution sln;
	//	nums = { 3,6,9 }, k = 3;
	//	auto res = sln.findKthSmallest(nums, k);
	//	Assert(9LL, res);
	//}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

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