LC 3444. Minimum Increments for Target Multiples in an Array

https://leetcode.com/problems/minimum-increments-for-target-multiples-in-an-array/description/

Tag: DP

typedef long long ll;
class Solution {
public:
    int minimumIncrements(vector<int>& nums, vector<int>& target) {
        int m = nums.size();
        int n = target.size();
        vector<ll> record(1 << n);
        for (int i = 0; i < (1 << n); i++) {
            ll need = 1;
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) need = lcm(need, target[j]);
            }
            record[i] = need;
        }
        vector<ll> f(1 << n, LLONG_MAX);
        f[0] = 0;
        for (auto &x: nums) {
            for (int pre = (1 << n) - 1; pre >= 0; pre--) {
                if (f[pre] == LLONG_MAX) continue;
                for (int cur = (1 << n) - 1; cur >= 0; cur--) {
                    if (pre == cur) continue;
                    if (pre != (pre & cur)) continue;
                    ll target = 1ll * (x / record[pre ^ cur] + ((x % record[pre ^ cur]) != 0)) * record[pre ^ cur];
                    f[cur] = min(f[cur], f[pre] + target - x);
                }
            }
        }
        return f.back();
    }
};

基礎的狀態壓縮 DP，根據題目可以知道 Target 的種類就只有 4 種，所以可以透過壓縮 DP 來表示，在 index 為 i 的情況下完成某幾個 Target 所需的操作次數。