LeetCode 3444.使数组包含目标值倍数的最小增量

给你两个数组 nums 和 target 。

在一次操作中，你可以将 nums 中的任意一个元素递增 1 。

返回要使 target 中的每个元素在 nums 中 至少 存在一个倍数所需的 最少操作次数 。

示例 1：

输入：nums = [1,2,3], target = [4]

输出：1

解释：

满足题目条件的最少操作次数是 1 。

将 3 增加到 4 ，需要 1 次操作，4 是目标值 4 的倍数。
示例 2：

输入：nums = [8,4], target = [10,5]

输出：2

解释：

满足题目条件的最少操作次数是 2 。

将 8 增加到 10 ，需要 2 次操作，10 是目标值 5 和 10 的倍数。
示例 3：

输入：nums = [7,9,10], target = [7]

输出：0

解释：

数组中已经包含目标值 7 的一个倍数，不需要执行任何额外操作。

提示：

1 <= nums.length <= 5 * 10^4
1 <= target.length <= 4
target.length <= nums.length
1 <= nums[i], target[i] <= 10^4

题目想要让target中每个数都能在nums中找到一个倍数，比如target中有两个数3、5，那么需要nums中有一个数是3、5的最小公倍数的倍数，即15的倍数，如果target中的数是5、10，那么需要nums中有一个数是10的倍数，因此我们可以先计算出target中所有非空子集的最小公倍数，然后用暴力法dp，我们可以遍历nums中的所有数字，当前数字可以进行增加操作，也可以不进行增加操作，如果不对当前数字进行增加操作，就相当于nums中少了一个数字，问题变成了规模更小的同样问题；如果对当前数字进行增加操作，就找到target的每个非空子集使当前数字的增量，然后从target中去掉对应的非空子集，从num中去掉当前数字，问题又变成了规模更小的同样问题。

C++解法：

class Solution {
public:int minimumIncrements(vector<int>& nums, vector<int>& target) {int m = target.size();// 一共有2^m个target的非空子集vector<long long> lcms(1 << m, 1);// 计算每个非空子集的lcmfor (int i = 0; i < m; ++i) {int curBit = 1 << i;for (int j = 0; j < curBit; ++j) {lcms[j | curBit] = lcm(target[i], lcms[j]);}}// tmp保存中间结果，防止dfs溢出vector tmp(nums.size(), vector<long long>(1 << m, -1));// i是当前遍历到的nums数组位置，倒序遍历// j是target的子集，j的第n位的二进制为1表示第n个数字在集合中auto dfs = [&](this auto &&dfs, int i, int j) -> long long {// 如果没有子集了，返回0，表示不再需要增量if (j == 0) {return 0;}// 如果nums遍历完了，但还有target子集，则此次dfs作废，返回一个大数即可if (i < 0) {// 除2防止溢出return numeric_limits<long long>::max() / 2;}// res是引用long long &res = tmp[i][j];if (res != -1) {return res;}// 不修改当前遍历到的数字res = dfs(i - 1, j);int jBak = j;// 每次jBak & (j - 1)，可以让j的二进制位中最右边的1变为0for (; j; j = jBak & (j - 1)) {// 选中每个子集，并修改当前数字，然后删去选中的数字和当前数字，继续dfs// jBak ^ j相当于二进制差集// (lcms[j] - nums[i] % lcms[j]) % lcms[j]作用是找出// nums[i]变为lcms[j]的倍数所需要的增量res = min(res, dfs(i - 1, jBak ^ j) + (lcms[j] - nums[i] % lcms[j]) % lcms[j]); }return res;};return dfs(nums.size() - 1, (1 << m) - 1);}
};

go解法：

func minimumIncrements(nums []int, target []int) int {n := len(nums)m := len(target)lcms := make([]int, 1 << m)lcms[0] = 1for i, v := range target {j := 1 << ifor k := 0; k < j; k++ {lcms[k | j] = lcm(v, lcms[k])} }tmp := make([][]int, n)for i := range tmp {tmp[i] = make([]int, 1 << m)for j := range tmp[i] {tmp[i][j] = -1}}var dfs func(int, int) intdfs = func(i, j int) (res int) {if (j == 0) {return 0}if (i < 0) {return math.MaxInt / 2}p := &tmp[i][j]if (*p != -1) {return *p}defer func() { *p = res }()res = dfs(i - 1, j)jBak := jfor ; j != 0; j = (j - 1) & jBak {res = min(res, dfs(i - 1, j ^ jBak) + (lcms[j] - nums[i] % lcms[j]) % lcms[j])}return res}return dfs(n - 1, (1 << m) - 1)
}func gcd(a, b int) int {for b != 0 {a, b = b, a % b}return a
}func lcm(a, b int) int {return a * b / gcd(a, b)
}

如果nums的长度为m，target的长度为n，那么计算所有lcm的过程的时间复杂度为O(2${}^m$)，而dfs的过程中，展开看相当于n次循环，每次循环了target子集的子集次，时间复杂度为O(n3${}^m$)，因此总的时间复杂度为O(n3${}^m$)。