Leetcode 3444. Minimum Increments for Target Multiples in an Array

• Leetcode 3444. Minimum Increments for Target Multiples in an Array
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3444. Minimum Increments for Target Multiples in an Array

1. 解题思路

这一题我的思路上就是一个深度优先遍历，考察target数组当中的每一个元素的全部倍数被出现的情况下，最少需要多少次操作，以及同时能够满足多少剩余的target数组中的数字，然后持续迭代考察，取其中的最小值。

同时，考虑到时间复杂度的因素，我们将结果用一个全局变量存下来，一旦某一步的结果超过了已知可行的最大操作数，就直接退出递归，从而进行剪枝。

2. 代码实现

给出最终的python代码实现如下：

class Solution:
    def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
        nums, target = sorted(nums), sorted(target, reverse=True)
        n, m = len(nums), len(target)
        status = [0 for _ in range(m)]
        ans = math.inf

        def dfs(idx, nums, status):
            nonlocal ans
            if idx >= m:
                return 0
            elif status[idx] == 1:
                return dfs(idx+1, nums, status)
            need = math.inf
            tgt = 0
            while tgt < nums[-1]:
                tgt += target[idx]
                old_status = deepcopy(status)
                for i, x in enumerate(target):
                    if status[i] == 1 or tgt % x == 0:
                        status[i] = 1
                i = bisect.bisect_right(nums, tgt)
                if i > 0:
                    num = nums.pop(i-1)
                    if abs(num-tgt) < ans:
                        need = min(need, abs(num-tgt) + dfs(idx+1, nums, status))
                    nums.insert(i-1, num)
                status = old_status
            if need >= ans:
                return math.inf
            if idx == 0:
                ans = need
            return need
        
        dfs(0, nums, status)
        return ans      

提交代码评测得到：耗时12ms，占用内存21.3MB。