这是 LeetCode 3444. 使数组包含目标值倍数的最少增量（Minimum Increments for Target Multiples in an Array）的 C++ 实现。

核心思路

子集状压 DP + 最小公倍数（LCM）

1. 预处理 LCM：`target` 长度 ≤ 4，枚举所有子集（最多 2^4 = 16 个），计算每个子集的最小公倍数 `lcms[mask]`。若一个 `nums[i]` 被增加到 `lcms[mask]` 的倍数，则它同时是 `mask` 中所有 `target` 元素的倍数。

2. 记忆化搜索：`dfs(i, j)` 表示考虑 `nums[0..i]`，还需要满足 `target` 的子集 `j`（位掩码）时的最小代价。
   - 不选 `nums[i]`：`dfs(i-1, j)`
   - 选 `nums[i]` 来满足 `j` 的某个非空子集 `sub`：代价为 `dfs(i-1, j ^ sub) + cost`，其中 `cost = (lcms[sub] - nums[i] % lcms[sub]) % lcms[sub]` 是将 `nums[i]` 增加到 `lcms[sub]` 倍数的最小增量。

3. 复杂度：O(n \cdot 3^m)，其中 m \leq 4，n \leq 5 \times 10^4，完全可行。

C++ 代码

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minimumIncrements(vector<int>& nums, vector<int>& target) {
        int m = target.size();
        int n = nums.size();

        // 预处理 target 所有子集的 LCM
        vector<long long> lcms(1 << m, 1);
        for (int i = 0; i < m; i++) {
            int bit = 1 << i;
            for (int mask = 0; mask < bit; mask++) {
                lcms[bit | mask] = lcm(target[i], lcms[mask]);
            }
        }

        // 记忆化搜索：memo[i][j] = -1 表示未计算
        vector<vector<long long>> memo(n, vector<long long>(1 << m, -1));
        long long ans = dfs(n - 1, (1 << m) - 1, nums, lcms, memo);
        return (int)ans;
    }

private:
    long long dfs(int i, int j, vector<int>& nums, vector<long long>& lcms,
                  vector<vector<long long>>& memo) {
        if (j == 0) {
            return 0; // 所有 target 都已满足
        }
        if (i < 0) {
            return LLONG_MAX / 2; // nums 用完但还有 target 未满足，非法
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        // 不选 nums[i]
        long long res = dfs(i - 1, j, nums, lcms, memo);

        // 选 nums[i] 来满足 j 的某个非空子集 sub
        int jBak = j;
        for (int sub = j; sub > 0; sub = (sub - 1) & jBak) {
            long long l = lcms[sub];
            long long cost = (l - nums[i] % l) % l; // 将 nums[i] 增加到 l 的倍数的最小代价
            res = min(res, dfs(i - 1, j ^ sub, nums, lcms, memo) + cost);
        }

        memo[i][j] = res;
        return res;
    }

    // 最大公约数
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 最小公倍数
    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
};
```

复杂度分析

- 时间复杂度：O(n \cdot 3^m)，m \leq 4，实际约为 O(81 \cdot n)
- 空间复杂度：O(n \cdot 2^m)，记忆化数组的空间