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.infdef dfs(idx, nums, status):nonlocal ansif idx >= m:return 0elif status[idx] == 1:return dfs(idx+1, nums, status)need = math.inftgt = 0while 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] = 1i = 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_statusif need >= ans:return math.infif idx == 0:ans = needreturn needdfs(0, nums, status)return ans      

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