本文涉及知识点
动态规划 区间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 <= 104
1 <= m == andValues.length <= min(n, 10)
1 <= nums[i] < 105
0 <= andValues[j] < 105
动态规划的位运算
动态规划
动态规划的状态表示
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∈ [ n e x t , n e x t 的下一个值 ) 这样值设置的时间复杂度是: \in[next,next的下一个值) 这样值设置的时间复杂度是:∈[next,next的下一个值)这样值设置的时间复杂度是: ,超时了。
只更新:x = next,其它的用二种方式更新:
如果 (nums[cur]& andValues[r-1]) = andValues[r-1]
则MinSelf(dp[r][cur],dp[r][cur-1])
时间复杂度:
动态规划的初始值
枚举第一个区间
动态规范的返回值
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; };
测试用例
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); //} }
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。