题目：
给你两个数组 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 <= 1041 <= m == andValues.length <= min(n, 10)1 <= nums[i] < 1050 <= andValues[j] < 105
思路：
寻找子问题
看示例 1，nums = [1,4,3,3,2], andValues = [0,3,3,2]。
我们要解决的问题是，把 nums 划分成 4 个子数组所能得到的最小子数组值之和，其中每个子数组的 AND 值与 andValues 中的值一一对应。
从 nums[0] 开始。考虑是否要把 nums[0] 作为子数组的最后一个数，分类讨论：
不把 nums[0] 作为子数组的最后一个数，也就是 nums[0] 和后续元素在同一个子数组中，那么接下来需要解决的问题为：把 [4,3,3,2] 划分成 4 个子数组，且第一个子数组与 nums[0] = 1 计算 AND 的值恰好等于 andValues[0] = 0，其余子数组的 AND 值分别等于 3, 3, 2，在满足该条件的情况下，所能得到的最小子数组值之和。
把 nums[0] 作为子数组的最后一个数，但子数组 AND 等于 1，不等于 andValues[0] = 0，不符合题目要求，无法划分。
继续。考虑是否要把 nums[1] 作为子数组的最后一个数，分类讨论：
不把 nums[1] 作为子数组的最后一个数，也就是 nums[1] 和后续元素在同一个子数组中，那么接下来需要解决的问题为：把 [3,3,2] 划分成 4 个子数组，且第一个子数组与 nums[0] & nums[1] 计算 AND 的值恰好等于 andValues[0] = 0，其余子数组的 AND 值分别等于 3, 3, 2，在满足该条件的情况下，所能得到的最小子数组值之和。注意剩余元素只有 3 个，没法分成 4 个子数组。
把 nums[1] 作为子数组的最后一个数，注意我们并不需要知道这个子数组的前面具体有哪些数，只需要知道前面的元素的 AND 值等于 1。由于 nums[0] & nums[1] = 1 & 4 = 0 = andValues[0]，符合题目要求，可以划分。接下来需要解决的问题为：把 [3, 3, 2] 划分成 3 个子数组，子数组的 AND 值分别等于 3, 3, 2，在满足该条件的情况下，所能得到的最小子数组值之和。
是否划分都会把原问题变成一个和原问题相似的、规模更小的子问题，都是把一些元素划分成若干段，且每一段的 AND 值与 andValues 中的元素匹配。这可以用递归解决。
注 1：为方便把子数组的最后一个元素加入答案，本题适合从左到右思考。
注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「选或不选」。
状态定义与状态转移方程
递归需要哪些参数？
需要知道当前考虑到 nums 的哪个数，其下标记作 i。
需要知道当前划分的子数组对应着 andValues 的哪个数，其下标记作 j。也可以理解为前面已经划分了 j 段。
需要知道当前划分的子数组，在 i 左边的那些元素的 AND 值，记作 and。再次强调，我们并不需要知道 i 左边具体有哪些数，只需要知道左边那些数的 AND 值是多少即可。
于是，定义 dfs(i, j, nd) 表示从左往右划分，目前考虑到 nums[i]，已经划分了 j 段，且当前待划分的这一段已经参与 AND 运算的结果为 and，在这种情况下，剩余元素划分得到的最小和。
首先把 and 与 nums[i] 计算 AND。
用「选或不选」的思想分类讨论：
不划分：继续向右递归 dfs(i + 1, j, and)。
划分：如果 and = andValues[j]，那么可以划分，即 dfs(i + 1, j + 1, −1) + nums[i]。这里令 and = −1 是因为 −1 的二进制全为 1，与任何数 x 的 AND 都是 x，适合用来计算新子数组的 AND 值。
这两种情况取最小值，就得到了 dfs(i,j,and)。
递归边界：
如果 n − i < m − j，那么剩余元素不足，无法划分，返回 ∞。
如果 j = m 且 i < n，还有元素没有划分，返回 ∞。
如果 j = m 且 i = n，划分成功，返回 0。
递归入口：dfs(0, 0, −1)，即答案。如果答案是 ∞ 则返回 −1。
代码：
class Solution {
public:
int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
const int INF = INT_MAX / 2; // 除 2 防止下面 + nums[i] 溢出
int n = nums.size(), m = andValues.size();
unordered_map<long long, int> memo;
auto dfs = [&](auto&& dfs, int i, int j, int and_) -> int {
if (n - i < m - j) { // 剩余元素不足
return INF;
}
if (j == m) { // 分了 m 段
return i == n ? 0 : INF;
}
and_ &= nums[i];
// 三个参数压缩成一个 long long
long long mask = (long long) i << 36 | (long long) j << 32 | and_;
if (memo.contains(mask)) { // 之前计算过
return memo[mask];
}
int res = dfs(dfs, i + 1, j, and_); // 不划分
if (and_ == andValues[j]) { // 划分，nums[i] 是这一段的最后一个数
res = min(res, dfs(dfs, i + 1, j + 1, -1) + nums[i]);
}
return memo[mask] = res; // 记忆化
};
int ans = dfs(dfs, 0, 0, -1);
return ans < INF ? ans : -1;
}
};