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

链接：3117.划分数组得到最小的值之和
难度：Hard
标签：位运算、线段树、队列、数组、二分查找、动态规划
简介：返回将 nums 划分为 m 个子数组所能得到的可能的最小子数组值之和。如果无法完成这样的划分，则返回 -1 。

题解 1 - python

编辑时间：2024-08-16
执行用时：1329ms
内存消耗：419.88MB
编程语言：python
解法介绍：dfs记录当前遍历到的两个数组下标和当前记录的与值

class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        nlen = len(nums)
        alen = len(andValues)
        @cache
        def dfs(nidx: int, aidx: int, val: int) -> int:
            if nidx == nlen: return 0 if aidx == alen else inf
            if aidx == alen: return inf
            if nlen - nidx < alen - aidx: return inf
            val &= nums[nidx]
            res = dfs(nidx + 1, aidx, val)
            if val == andValues[aidx]: res = min(res, dfs(nidx + 1, aidx + 1, -1) + nums[nidx])
            return res
        res = dfs(0, 0, -1)
        return res if res != inf else -1

题解 1 - python​

题解 1 - python