Hard

题目描述

给定两个长度分别为 n 和 m 的数组 nums 和 andValues。

数组的值等于该数组的最后一个元素。

你需要将 nums 分割成 m 个不相交的连续子数组，使得对于第 i 个子数组 [li, ri]，子数组元素的按位与等于 andValues[i]，换句话说，对于所有 1 <= i <= m，都有 nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i]，其中 & 表示按位与运算符。

返回将 nums 分成的 m 个子数组的值的最小可能和。如果无法将 nums 分成满足这些条件的 m 个子数组，则返回 -1。

示例 1:

输入: nums = [1,4,3,3,2], andValues = [0,3,3,2]
输出: 12
解释:
唯一可能的分割方式是:
[1,4] 因为 1 & 4 == 0
[3] 因为单个元素子数组的按位与就是该元素本身
[3] 因为单个元素子数组的按位与就是该元素本身
[2] 因为单个元素子数组的按位与就是该元素本身
这些子数组的值的和是 4 + 3 + 3 + 2 = 12

示例 2:

输入: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]
输出: 17
解释:
有三种分割方式:
[[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 的按位与是 0。由于无法将 nums 分成一个子数组使得元素的按位与为 2，因此返回 -1

约束条件:

  • 1 <= n == nums.length <= 10^4
  • 1 <= m == andValues.length <= min(n, 10)
  • 1 <= nums[i] < 10^5
  • 0 <= andValues[j] < 10^5

解题思路

这是一道动态规划 + 位运算优化的难题。核心思路如下：

问题分析：我们需要将数组分成 m 段，每段的按位与值要等于对应的 andValues 值，目标是最小化各段末尾元素的和。

动态规划状态设计：定义 dp[i][j] 表示将前 i 个元素分成 j 段的最小值和。状态转移方程为： dp[i][j] = min(dp[k][j-1]) + nums[i-1]，其中 k 需要满足从 k+1 到 i 的子数组按位与等于 andValues[j-1]。

关键优化：

  1. 按位与性质：按位与运算具有单调性，随着元素增加，结果只会保持不变或变小，不会增大
  2. 二分查找：对于每个位置 i 和段数 j，可以用二分查找找到满足按位与条件的区间范围
  3. 单调队列优化：由于查询的是滑动窗口内的最小值，可以用单调队列代替线段树，降低复杂度

算法流程：

  • 初始化 dp[0][0] = 0，其他位置为无穷大
  • 对于每个位置和段数，计算满足按位与条件的有效区间
  • 使用单调队列维护区间最小值，更新状态

由于按位与的特殊性质，实际的状态数会比理论上限少很多，使得算法在实践中表现良好。

代码实现

class Solution {
public:
    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
        int n = nums.size(), m = andValues.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int j = 1; j <= m; j++) {
            for (int i = j; i <= n; i++) {
                // 找到以位置i结尾，按位与值等于andValues[j-1]的区间范围
                int left = i, right = -1;
                int andVal = nums[i-1];
                
                // 向左扩展找到最长的满足条件的区间
                for (int k = i - 1; k >= j - 1; k--) {
                    if (k < i - 1) andVal &= nums[k];
                    if (andVal == andValues[j-1]) {
                        left = k + 1;
                        if (right == -1) right = k + 1;
                    } else if (andVal < andValues[j-1]) {
                        break;
                    }
                }
                
                // 更新dp值
                if (right != -1) {
                    for (int k = left; k <= right; k++) {
                        if (dp[k-1][j-1] != INT_MAX) {
                            dp[i][j] = min(dp[i][j], dp[k-1][j-1] + nums[i-1]);
                        }
                    }
                }
            }
        }
        
        return dp[n][m] == INT_MAX ? -1 : dp[n][m];
    }
};

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        n, m = len(nums), len(andValues)
        dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for j in range(1, m + 1):
            for i in range(j, n + 1):
                # 找到以位置i结尾，按位与值等于andValues[j-1]的区间范围
                left, right = i, -1
                and_val = nums[i-1]
                
                # 向左扩展找到最长的满足条件的区间
                for k in range(i - 1, j - 2, -1):
                    if k < i - 1:
                        and_val &= nums[k]
                    if and_val == andValues[j-1]:
                        left = k + 1
                        if right == -1:
                            right = k + 1
                    elif and_val < andValues[j-1]:
                        break
                
                # 更新dp值
                if right != -1:
                    for k in range(left, right + 1):
                        if dp[k-1][j-1] != float('inf'):
                            dp[i][j] = min(dp[i][j], dp[k-1][j-1] + nums[i-1])
        
        return dp[n][m] if dp[n][m] != float('inf') else -1

public class Solution {
    public int MinimumValueSum(int[] nums, int[] andValues) {
        int n = nums.Length, m = andValues.Length;
        int[,] dp = new int[n + 1, m + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int j = 1; j <= m; j++) {
            for (int i = j; i <= n; i++) {
                // 找到以位置i结尾，按位与值等于andValues[j-1]的区间范围
                int left = i, right = -1;
                int andVal = nums[i-1];
                
                // 向左扩展找到最长的满足条件的区间
                for (int k = i - 1; k >= j - 1; k--) {
                    if (k < i - 1) andVal &= nums[k];
                    if (andVal == andValues[j-1]) {
                        left = k + 1;
                        if (right == -1) right = k + 1;
                    } else if (andVal < andValues[j-1]) {
                        break;
                    }
                }
                
                // 更新dp值
                if (right != -1) {
                    for (int k = left; k <= right; k++) {
                        if (dp[k-1, j-1] != int.MaxValue) {
                            dp[i, j] = Math.Min(dp[i, j], dp[k-1, j-1] + nums[i-1]);
                        }
                    }
                }
            }
        }
        
        return dp[n, m] == int.MaxValue ? -1 : dp[n, m];
    }
}

var minimumValueSum = function(nums, andValues) {
    const n = nums.length;
    const m = andValues.length;
    const memo = new Map();
    
    function dp(i, j, currentAnd) {
        if (j === m) {
            return i === n ? 0 : Infinity;
        }
        if (i === n) {
            return Infinity;
        }
        
        const key = `${i},${j},${currentAnd}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        const newAnd = currentAnd & nums[i];
        let result = Infinity;
        
        // Continue current subarray
        if (newAnd >= andValues[j]) {
            result = Math.min(result, dp(i + 1, j, newAnd));
        }
        
        // End current subarray if AND matches
        if (newAnd === andValues[j]) {
            result = Math.min(result, nums[i] + dp(i + 1, j + 1, (1 << 17) - 1));
        }
        
        memo.set(key, result);
        return result;
    }
    
    const result = dp(0, 0, (1 << 17) - 1);
    return result === Infinity ? -1 : result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²m)
空间复杂度O(nm)

注：实际时间复杂度会因为按位与运算的特性而有所优化，在大多数情况下表现更好。

相关题目