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

简介: 【动态规划 区间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 <= 104

1 <= m == andValues.length <= min(n, 10)

1 <= nums[i] < 105

0 <= andValues[j] < 105

动态规划的位运算

image.png

动态规划

动态规划的状态表示

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的下一个值)这样值设置的时间复杂度是: image.png ,超时了。

只更新:x = next,其它的用二种方式更新:

如果 (nums[cur]& andValues[r-1]) = andValues[r-1]

则MinSelf(dp[r][cur],dp[r][cur-1])

时间复杂度: image.png

动态规划的初始值

枚举第一个区间

动态规范的返回值

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++**实现。

相关文章
|
6月前
|
算法 测试技术 C#
【贪心】【分类讨论】2499. 让数组不相等的最小总代价
【贪心】【分类讨论】2499. 让数组不相等的最小总代价
|
6月前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目
|
6月前
|
算法
|
6月前
|
机器学习/深度学习 算法 测试技术
【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数
【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数
|
6月前
DAY-4 | 力扣 - 求自身以外数组的乘积:区间划分,左右累乘,巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法,一是暴力破解,即计算所有数的乘积后再逐个除以当前元素;二是左右累乘法,通过两次遍历数组分别计算左侧和右侧元素的乘积,避免了除法操作。其中,左右累乘法更优,代码实现中展示了这种方法。
43 1
|
5月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6月前
【编程题-错题集】连续子数组最大和(动态规划 - 线性 dp)
【编程题-错题集】连续子数组最大和(动态规划 - 线性 dp)
|
6月前
|
算法 测试技术 C#
【线段树 区间位运算模板】3117划分数组得到最小的值之和
【线段树 区间位运算模板】3117划分数组得到最小的值之和
|
6月前
|
算法 测试技术 C#
【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目
【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目
|
6月前
|
算法 测试技术 C++
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数