↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-3117 划分数组得到最小的值之和 #

Solution 1 #

对于 $nums[i]$ , 如果不将它作为第 $j$ 的划分为结尾, 那么后面的划分和它的按位与结果应当等于 $andValue[j]$ . 因此我们保存三个状态 $(i, j, and_res)$ , 分别代表当前进行到 $nums[i]$ , 考虑划分出 $andValue[j]$ , 并且前面包含的这个划分的元素的按位与结果为 $and_res$ . 状态转移方程: $$ f(i, j, and_res)=\begin{cases} f(i + 1, j, and_res & nums[i]),\ if\ and_res& nums[i] \not = andValue[j]\ \min(f(i + 1, j, and_res & nums[i]), f(i + 1, j + 1, -1)),\ if\ and_res& nums[i] = andValue[j]\ \end{cases} $$

代码如下:

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        n, m = len(nums), len(andValues)

        @cache
        def f(i, j, and_res):
            if n - i < m - j:
                return inf
            if j == m:
                return inf if i < n else 0
            and_res &= nums[i]
            res = f(i + 1, j, and_res)
            if and_res == andValues[j]:
                res = min(res, f(i + 1, j + 1, -1) + nums[i])
            return res

        return -1 if f(0, 0, -1) == inf else f(0, 0, -1)