Hard
题目描述
给你两个数组 nums 和 target。
在一次操作中，你可以将 nums 中的任何一个元素增加 1。
返回使得 target 中每个元素在 nums 中都至少有一个倍数所需的最小操作次数。
示例 1：
输入：nums = [1,2,3], target = [4]
输出：1
解释：
满足条件所需的最小操作次数是 1。
将 3 增加到 4，只需一次操作，使 4 成为自身的倍数。
示例 2：
输入：nums = [8,4], target = [10,5]
输出：2
解释：
满足条件所需的最小操作次数是 2。
将 8 增加到 10，需要 2 次操作，使 10 成为 5 和 10 的倍数。
示例 3：
输入：nums = [7,9,10], target = [7]
输出：0
解释：
目标 7 在 nums 中已经有倍数，因此不需要额外的操作。
约束条件：
1 <= nums.length <= 5 * 10^41 <= target.length <= 4target.length <= nums.length1 <= nums[i], target[i] <= 10^4
解题思路
这是一个经典的状态压缩动态规划问题。由于 target 数组长度最多为 4，我们可以使用位掩码来表示已经满足的目标元素集合。
核心思路：
- 状态压缩：使用位掩码
mask表示已经满足的目标元素，第i位为 1 表示target[i]已经有倍数 - 动态规划：
dp[i][mask]表示处理前i个nums元素，满足状态mask的最小操作次数 - 状态转移：对于每个
nums[i]，我们可以选择不修改，或者增加到某个值使其成为某些目标的倍数
优化策略：
- 对于每个目标值，我们只需要考虑将
nums[i]增加到不超过target[j] * 2的范围内的倍数 - 使用位运算快速计算新的满足状态
算法步骤：
- 初始化 DP 数组，
dp[0][0] = 0 - 对每个
nums[i]，枚举所有可能的状态转移 - 对每个状态，计算将当前数增加到各个目标倍数的代价
- 返回
dp[n][(1 << target.size()) - 1]
代码实现
class Solution {
public:
int minimumIncrements(vector<int>& nums, vector<int>& target) {
int n = nums.size();
int m = target.size();
int maxMask = (1 << m) - 1;
vector<vector<int>> dp(n + 1, vector<int>(1 << m, INT_MAX));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
for (int mask = 0; mask <= maxMask; mask++) {
if (dp[i][mask] == INT_MAX) continue;
// Option 1: Don't change nums[i]
int newMask = mask;
for (int j = 0; j < m; j++) {
if (nums[i] % target[j] == 0) {
newMask |= (1 << j);
}
}
dp[i + 1][newMask] = min(dp[i + 1][newMask], dp[i][mask]);
// Option 2: Increase nums[i] to satisfy some targets
for (int submask = 1; submask <= maxMask; submask++) {
int cost = 0;
int candidate = nums[i];
bool valid = true;
for (int j = 0; j < m; j++) {
if (submask & (1 << j)) {
int needed = ((nums[i] + target[j] - 1) / target[j]) * target[j];
candidate = max(candidate, needed);
}
}
// Check if this candidate satisfies all bits in submask
for (int j = 0; j < m; j++) {
if ((submask & (1 << j)) && candidate % target[j] != 0) {
valid = false;
break;
}
}
if (valid && candidate - nums[i] <= 10000) {
cost = candidate - nums[i];
int newMask2 = mask | submask;
dp[i + 1][newMask2] = min(dp[i + 1][newMask2], dp[i][mask] + cost);
}
}
}
}
return dp[n][maxMask];
}
};
class Solution:
def minimumIncrements(self, nums: List[int], target: List[int]) -> int:
n, m = len(nums), len(target)
max_mask = (1 << m) - 1
dp = [[float('inf')] * (1 << m) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
for mask in range(1 << m):
if dp[i][mask] == float('inf'):
continue
# Option 1: Don't change nums[i]
new_mask = mask
for j in range(m):
if nums[i] % target[j] == 0:
new_mask |= (1 << j)
dp[i + 1][new_mask] = min(dp[i + 1][new_mask], dp[i][mask])
# Option 2: Increase nums[i] to satisfy some targets
for submask in range(1, 1 << m):
candidate = nums[i]
valid = True
for j in range(m):
if submask & (1 << j):
needed = ((nums[i] + target[j] - 1) // target[j]) * target[j]
candidate = max(candidate, needed)
# Check if this candidate satisfies all bits in submask
for j in range(m):
if (submask & (1 << j)) and candidate % target[j] != 0:
valid = False
break
if valid and candidate - nums[i] <= 10000:
cost = candidate - nums[i]
new_mask2 = mask | submask
dp[i + 1][new_mask2] = min(dp[i + 1][new_mask2], dp[i][mask] + cost)
return dp[n][max_mask]
public class Solution {
public int MinimumIncrements(int[] nums, int[] target) {
int n = nums.Length;
int m = target.Length;
int maxMask = (1 << m) - 1;
int[,] dp = new int[n + 1, 1 << m];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < (1 << m); j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0;
for (int i = 0; i < n; i++) {
for (int mask = 0; mask <= maxMask; mask++) {
if (dp[i, mask] == int.MaxValue) continue;
// Option 1: Don't change nums[i]
int newMask = mask;
for (int j = 0; j < m; j++) {
if (nums[i] % target[j] == 0) {
newMask |= (1 << j);
}
}
dp[i + 1, newMask] = Math.Min(dp[i + 1, newMask], dp[i, mask]);
// Option 2: Increase nums[i] to satisfy some targets
for (int submask = 1; submask <= maxMask; submask++) {
int candidate = nums[i];
bool valid = true;
for (int j = 0; j < m; j++) {
if ((submask & (1 << j)) != 0) {
int needed = ((nums[i] + target[j] - 1) / target[j]) * target[j];
candidate = Math.Max(candidate, needed);
}
}
// Check if this candidate satisfies all bits in submask
for (int j = 0; j < m; j++) {
if ((submask & (1 << j)) != 0 && candidate % target[j] != 0) {
valid = false;
break;
}
}
if (valid && candidate - nums[i] <= 10000) {
int cost = candidate - nums[i];
int newMask2 = mask | submask;
dp[i + 1, newMask2] = Math.Min(dp[i + 1, newMask2], dp[i, mask] + cost);
}
}
}
}
return dp[n, maxMask];
}
}
var minimumIncrements = function(nums, target) {
const n = nums.length;
const m = target.length;
// Generate all possible subsets of target
const subsets = [];
for (let mask = 1; mask < (1 << m); mask++) {
const subset = [];
for (let i = 0; i < m; i++) {
if (mask & (1 << i)) {
subset.push(target[i]);
}
}
subsets.push(subset);
}
// For each subset, find the LCM
const lcms = subsets.map(subset => {
let lcm = subset[0];
for (let i = 1; i < subset.length; i++) {
lcm = (lcm * subset[i]) / gcd(lcm, subset[i]);
}
return lcm;
});
// DP with bitmask
const dp = new Array(1 << m).fill(Infinity);
dp[0] = 0;
nums.sort((a, b) => a - b);
for (const num of nums) {
const newDp = [...dp];
for (let mask = 0; mask < (1 << m); mask++) {
if (dp[mask] === Infinity) continue;
// Try to use this num for each subset
for (let i = 0; i < subsets.length; i++) {
const subset = subsets[i];
const subsetMask = subset.reduce((acc, val) => {
return acc | (1 << target.indexOf(val));
}, 0);
if ((mask & subsetMask) === 0) { // No overlap
const lcm = lcms[i];
const cost = Math.max(0, lcm - num);
if (cost <= 10000) { // Reasonable bound
const nextMask = mask | subsetMask;
newDp[nextMask] = Math.min(newDp[nextMask], dp[mask] + cost);
}
}
}
}
dp.splice(0, dp.length, ...newDp);
}
return dp[(1 << m) - 1];
};
function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × 2^m × 2^m × m) = O(n × 4^m × m)，其中 n 是 nums 长度，m 是 target 长度 |
| 空间复杂度 | O(n × 2^m)，动态规划数组的空间 |