LeetCode 3444: Minimum Increments for Target Multiples in an Array (Bitmask DP + LCM)
LeetCode 3444Source: https://leetcode.com/problems/minimum-increments-for-target-multiples-in-an-array/
English
Let m = target.length. For every non-empty subset of target, precompute its LCM. If we use one number x to satisfy that subset, required increments are (lcm - x % lcm) % lcm. Then run bitmask DP: dp[mask] is minimum cost to cover target indices in mask. For each x in nums, try assigning it to any subset and relax transitions.
class Solution {
private static final long INF = (long) 4e18;
public int minimumIncrements(int[] nums, int[] target) {
int m = target.length;
int full = 1 << m;
long[] subsetLcm = new long[full];
subsetLcm[0] = 1;
for (int mask = 1; mask < full; mask++) {
long l = 1;
boolean overflow = false;
for (int i = 0; i < m; i++) {
if (((mask >> i) & 1) == 1) {
l = lcmCap(l, target[i], INF);
if (l >= INF) {
overflow = true;
break;
}
}
}
subsetLcm[mask] = overflow ? INF : l;
}
long[] dp = new long[full];
java.util.Arrays.fill(dp, INF);
dp[0] = 0;
for (int x : nums) {
long[] ndp = dp.clone();
for (int mask = 0; mask < full; mask++) {
if (dp[mask] >= INF) continue;
for (int sub = 1; sub < full; sub++) {
long l = subsetLcm[sub];
if (l >= INF) continue;
long add = (l - (x % l)) % l;
int nmask = mask | sub;
ndp[nmask] = Math.min(ndp[nmask], dp[mask] + add);
}
}
dp = ndp;
}
return (int) dp[full - 1];
}
private long gcd(long a, long b) {
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}
private long lcmCap(long a, long b, long cap) {
long g = gcd(a, b);
long t = a / g;
if (t > cap / b) return cap;
return t * b;
}
}from math import gcd
from typing import List
class Solution:
def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
m = len(target)
full = 1 << m
INF = 10**30
subset_lcm = [1] * full
for mask in range(1, full):
l = 1
for i in range(m):
if (mask >> i) & 1:
l = l // gcd(l, target[i]) * target[i]
if l >= INF:
l = INF
break
subset_lcm[mask] = l
dp = [INF] * full
dp[0] = 0
for x in nums:
ndp = dp[:]
for mask in range(full):
if dp[mask] >= INF:
continue
for sub in range(1, full):
l = subset_lcm[sub]
if l >= INF:
continue
add = (l - x % l) % l
nmask = mask | sub
ndp[nmask] = min(ndp[nmask], dp[mask] + add)
dp = ndp
return dp[full - 1]中文
令 m = target.length。先枚举 target 的所有非空子集并预处理其最小公倍数 LCM。若用某个 x 去满足该子集，最少递增次数是 (LCM - x % LCM) % LCM。然后做状态压缩 DP：dp[mask] 表示覆盖了目标下标集合 mask 的最小代价。遍历 nums 中每个数，尝试让它覆盖任意子集并更新答案。
class Solution {
private static final long INF = (long) 4e18;
public int minimumIncrements(int[] nums, int[] target) {
int m = target.length;
int full = 1 << m;
long[] subsetLcm = new long[full];
subsetLcm[0] = 1;
for (int mask = 1; mask < full; mask++) {
long l = 1;
boolean overflow = false;
for (int i = 0; i < m; i++) {
if (((mask >> i) & 1) == 1) {
l = lcmCap(l, target[i], INF);
if (l >= INF) {
overflow = true;
break;
}
}
}
subsetLcm[mask] = overflow ? INF : l;
}
long[] dp = new long[full];
java.util.Arrays.fill(dp, INF);
dp[0] = 0;
for (int x : nums) {
long[] ndp = dp.clone();
for (int mask = 0; mask < full; mask++) {
if (dp[mask] >= INF) continue;
for (int sub = 1; sub < full; sub++) {
long l = subsetLcm[sub];
if (l >= INF) continue;
long add = (l - (x % l)) % l;
int nmask = mask | sub;
ndp[nmask] = Math.min(ndp[nmask], dp[mask] + add);
}
}
dp = ndp;
}
return (int) dp[full - 1];
}
private long gcd(long a, long b) {
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}
private long lcmCap(long a, long b, long cap) {
long g = gcd(a, b);
long t = a / g;
if (t > cap / b) return cap;
return t * b;
}
}from math import gcd
from typing import List
class Solution:
def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
m = len(target)
full = 1 << m
INF = 10**30
subset_lcm = [1] * full
for mask in range(1, full):
l = 1
for i in range(m):
if (mask >> i) & 1:
l = l // gcd(l, target[i]) * target[i]
if l >= INF:
l = INF
break
subset_lcm[mask] = l
dp = [INF] * full
dp[0] = 0
for x in nums:
ndp = dp[:]
for mask in range(full):
if dp[mask] >= INF:
continue
for sub in range(1, full):
l = subset_lcm[sub]
if l >= INF:
continue
add = (l - x % l) % l
nmask = mask | sub
ndp[nmask] = min(ndp[nmask], dp[mask] + add)
dp = ndp
return dp[full - 1]
Comments