🚩 题目链接
⛲ 题目描述
给你两个数组 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
🌟 求解思路&实现代码&运行结果
⚡ 动态规划
🥦 求解思路
- 看到这题，想到的解法就是从i位置开始进行划分，已经划分j段，此时&运算的结果是cur，找到划分后得到的最小和。
- 每一个位置可以选，或者不选，注意，这里的选和不选指的是，是否进行划分，假设当前位置不选，也就是不进行划分，我们进行与运算cur &=nums[i]，继续过程i+1，j，cur。
- 如果当前cur等于划分的结果了，此时必须进行划分，此时我们来到i+1，j+1，同时cur归到-1的位置，为什么是-1，因为-1 & x = x。同时，更新最小的值。
- 有了基本的思路，接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
private int n;
private int m;
private int[] nums;
private int[] andValues;
private HashMap<String, Integer> map;
public int minimumValueSum(int[] nums, int[] andValues) {
this.n = nums.length;
this.m = andValues.length;
this.nums = nums;
this.andValues = andValues;
this.map = new HashMap<>();
int ans = dfs(0, 0, -1);
return ans == Integer.MAX_VALUE / 2 ? -1 : ans;
}
public int dfs(int i, int j, int cur) {
if (m - j > n - i)
return Integer.MAX_VALUE / 2;
if (j == m) {
return i == n ? 0 : Integer.MAX_VALUE / 2;
}
// 不选
cur &= nums[i];
if (cur < andValues[j])
return Integer.MAX_VALUE / 2;
String key = i + "@" + j + "@" + cur;
if (map.containsKey(key)) {
return map.get(key);
}
int ans = dfs(i + 1, j, cur);
// 选
if (cur == andValues[j]) {
ans = Math.min(ans, dfs(i + 1, j + 1, -1) + nums[i]);
}
map.put(key, ans);
return ans;
}
}