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

核心思路

子集状压 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，完全可行。

Python3 代码

```python
import math
from functools import lru_cache

class Solution:
    def minimumIncrements(self, nums: list[int], target: list[int]) -> int:
        m = len(target)
        n = len(nums)

        # 预处理 target 所有子集的 LCM
        lcms = [1] * (1 << m)
        for i in range(m):
            bit = 1 << i
            for mask in range(bit):
                lcms[bit | mask] = (target[i] * lcms[mask]) // math.gcd(target[i], lcms[mask])

        @lru_cache(maxsize=None)
        def dfs(i: int, j: int) -> int:
            if j == 0:
                return 0  # 所有 target 都已满足
            if i < 0:
                return float('inf')  # nums 用完但还有 target 未满足，非法

            # 不选 nums[i]
            res = dfs(i - 1, j)

            # 选 nums[i] 来满足 j 的某个非空子集 sub
            j_bak = j
            sub = j
            while sub > 0:
                l = lcms[sub]
                cost = (l - nums[i] % l) % l  # 将 nums[i] 增加到 l 的倍数的最小代价
                res = min(res, dfs(i - 1, j ^ sub) + cost)
                sub = (sub - 1) & j_bak

            return res

        return dfs(n - 1, (1 << m) - 1)
```

复杂度分析

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