How do I approach solving the Minimum Sum of Values by Dividing Array problem?

Focus on dynamic programming, where you keep track of the optimal subarray splits and calculate the bitwise AND for each subarray to match andValues.

What is the most efficient way to calculate the bitwise AND for subarrays?

Use a running AND calculation as you extend the subarray, avoiding redundant recalculations by keeping track of the last AND value.

What happens if it's impossible to split nums as required in the problem?

If no valid division can be made, return -1 to indicate it's impossible to achieve the required subarrays.

How do I optimize the dynamic programming approach for this problem?

Ensure that you minimize redundant calculations in the DP table by efficiently updating the state transitions and checking each subarray's AND value against the corresponding entry in andValues.

What should I do if the number of subarrays is different from the length of andValues?

The number of subarrays must match the length of andValues. If they don't, a valid solution cannot be found, and the answer should be -1.

#3117

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

划分数组得到最小的值之和

给你两个数组 nums 和 andValues ，长度分别为 n 和 m 。数组的值等于该数组的最后一个元素。你需要将 nums 划分为 m 个不相交的连续子数组，对于第 i th 个子数组 [l i , r i ] ，子数组元素的按位 AND 运算结果等于 andValues[i…

数组二分查找动态规划位运算线段树

题目描述

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

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

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 i^th 个子数组 [l_i, r_i]，子数组元素的按位 AND 运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[l_i] & nums[l_i + 1] & ... & nums[r_i] == 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 <= 10⁴
1 <= m == andValues.length <= min(n, 10)
1 <= nums[i] < 10⁵
0 <= andValues[j] < 10⁵

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j, a)$ ，表示从第 $i$ 个元素开始，当前已经划分了 $j$ 个子数组，且当前待划分的子数组的按位与结果为 $a$ 的情况下，所能得到的可能的最小子数组值之和。那么答案就是 $dfs(0, 0, -1)$ 。

函数 $dfs(i, j, a)$ 的执行过程如下：

如果 $n - i < m - j$ ，那么说明剩下的元素不足以划分出 $m - j$ 个子数组，返回 $+\infty$ 。
如果 $j = m$ ，那么说明已经划分出了 $m$ 个子数组，此时判断 $i = n$ 是否成立，如果成立返回 $0$ ，否则返回 $+\infty$ 。
否则，我们将 $a$ $a$ 与 $nums[i]$ $n u m s [i]$ 进行按位与操作，得到新的 $a$ $a$ 。如果 $a < andValues[j]$ $a < an d V a l u es [j]$ ，那么说明当前待划分的子数组的按位与结果不满足要求，返回 $+\infty$ $+ \infty$ 。否则，我们有两种选择：
- 不划分当前元素，即 $dfs(i + 1, j, a)$ 。
- 划分当前元素，即 $dfs(i + 1, j + 1, -1) + nums[i]$ 。
返回上述两种选择的最小值。

为了避免重复计算，我们使用记忆化搜索的方法，将 $dfs(i, j, a)$ 的结果存储在一个哈希表中。

时间复杂度 $O(n \times m \times \log M)$ ，空间复杂度 $O(n \times m \times \log M)$ 。其中 $n$ 和 $m$ 分别是数组 $nums$ 和 $andValues$ 的长度；而 $M$ 是数组 $nums$ 中的最大值，本题中 $M \leq 10^5$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, a: int) -> int:
            if n - i < m - j:
                return inf
            if j == m:
                return 0 if i == n else inf
            a &= nums[i]
            if a < andValues[j]:
                return inf
            ans = dfs(i + 1, j, a)
            if a == andValues[j]:
                ans = min(ans, dfs(i + 1, j + 1, -1) + nums[i])
            return ans

        n, m = len(nums), len(andValues)
        ans = dfs(0, 0, -1)
        return ans if ans < inf else -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate is familiar with dynamic programming for state transitions.
question_mark
Candidate understands bitwise operations and how they apply to subarrays.
question_mark
Candidate optimizes the solution by avoiding redundant calculations and efficiently updating states.

warning

常见陷阱

外企场景

error
Not handling edge cases where a valid division is impossible, returning -1 in such cases.
error
Overcomplicating the bitwise AND computation by recalculating for each subarray repeatedly.
error
Missing an efficient way to manage dynamic programming state transitions, leading to redundant operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where the number of subarrays is increased, making it necessary to optimize the DP approach.
arrow_right_alt
Differentiate the problem by changing the bitwise operation (e.g., OR instead of AND) and observe the impact on the solution.
arrow_right_alt
Change the problem constraints, such as limiting the size of nums or andValues, to explore how that affects the approach.

help

常见问题

外企场景

继续练习

#3171 找到按位或最接近 K 的子数组 #3209 子数组按位与值为 K 的数目 #2945 找到最大非递减数组的长度