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

核心思路

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

Rust 代码

```rust
use std::collections::HashMap;

impl Solution {
    pub fn minimum_increments(nums: Vec<i32>, target: Vec<i32>) -> i32 {
        let m = target.len();
        let n = nums.len();

        // 预处理 target 所有子集的 LCM
        let mut lcms = vec![1i64; 1 << m];
        for i in 0..m {
            let bit = 1 << i;
            for mask in 0..bit {
                lcms[bit | mask] = Self::lcm(target[i] as i64, lcms[mask]);
            }
        }

        // 记忆化搜索
        let mut memo: HashMap<(i32, i32), i64> = HashMap::new();

        fn dfs(
            i: i32,
            j: i32,
            nums: &[i32],
            lcms: &[i64],
            memo: &mut HashMap<(i32, i32), i64>,
        ) -> i64 {
            if j == 0 {
                return 0; // 所有 target 都已满足
            }
            if i < 0 {
                return i64::MAX / 2; // nums 用完但还有 target 未满足，非法
            }
            if let Some(&val) = memo.get(&(i, j)) {
                return val;
            }

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

            // 选 nums[i] 来满足 j 的某个非空子集 sub
            let j_bak = j;
            let mut sub = j;
            while sub > 0 {
                let l = lcms[sub as usize];
                let cost = (l - (nums[i as usize] as i64 % l)) % l;
                res = res.min(dfs(i - 1, j ^ sub, nums, lcms, memo) + cost);
                sub = (sub - 1) & j_bak;
            }

            memo.insert((i, j), res);
            res
        }

        let ans = dfs(n as i32 - 1, (1 << m) - 1, &nums, &lcms, &mut memo);
        ans as i32
    }

    // 最大公约数
    fn gcd(a: i64, b: i64) -> i64 {
        if b == 0 {
            a
        } else {
            Self::gcd(b, a % b)
        }
    }

    // 最小公倍数
    fn lcm(a: i64, b: i64) -> i64 {
        a / Self::gcd(a, b) * b
    }
}
```

复杂度分析

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