Medium
题目描述
给你一个整数数组 nums 和三个整数 k、op1 和 op2。
你可以对 nums 执行以下操作：
- 操作1：选择一个下标
i，将nums[i]除以 2，向上取整到最近的整数。你最多可以执行此操作op1次，每个下标最多一次。 - 操作2：选择一个下标
i，从nums[i]中减去k，但仅当nums[i]大于等于k时才能执行。你最多可以执行此操作op2次，每个下标最多一次。
注意：两种操作可以应用到同一个下标，但每种操作最多只能执行一次。
返回执行任意次操作后 nums 中所有元素的最小可能和。
示例 1：
输入：nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1
输出：23
解释：
- 对 nums[1] = 8 应用操作2，使 nums[1] = 5。
- 对 nums[3] = 19 应用操作1，使 nums[3] = 10。
- 结果数组为 [2, 5, 3, 10, 3]，应用操作后的最小可能和为 23。
示例 2：
输入：nums = [2,4,3], k = 3, op1 = 2, op2 = 1
输出：3
解释：
- 对 nums[0] = 2 应用操作1，使 nums[0] = 1。
- 对 nums[1] = 4 应用操作1，使 nums[1] = 2。
- 对 nums[2] = 3 应用操作2，使 nums[2] = 0。
- 结果数组为 [1, 2, 0]，最小可能和为 3。
约束：
1 <= nums.length <= 1000 <= nums[i] <= 10^50 <= k <= 10^50 <= op1, op2 <= nums.length
解题思路
这道题是一个典型的动态规划问题，需要考虑在每个位置如何分配有限的操作次数以达到最小和。
思路分析：
状态定义：使用三维DP，
dp[i][j1][j2]表示处理到第i个元素，还剩j1次操作1和j2次操作2时能达到的最小和。状态转移：对于每个元素，我们有以下选择：
- 不对当前元素执行任何操作
- 只执行操作1（除以2向上取整）
- 只执行操作2（减去k，需要满足条件）
- 先执行操作1再执行操作2
- 先执行操作2再执行操作1
关键观察：对于同一个元素，我们需要比较不同操作顺序的效果。由于操作1是除法，操作2是减法，先执行哪个操作会影响最终结果。
优化策略：对于每个元素，我们计算所有可能的操作组合结果，选择能使总和最小的方案。需要特别注意操作2的前提条件（元素值要大于等于k）。
推荐解法：使用记忆化搜索的动态规划，这样可以避免计算不必要的状态，提高效率。
代码实现
class Solution {
public:
int minArraySum(vector<int>& nums, int k, int op1, int op2) {
int n = nums.size();
vector<vector<vector<int>>> memo(n, vector<vector<int>>(op1 + 1, vector<int>(op2 + 1, -1)));
function<int(int, int, int)> dfs = [&](int idx, int o1, int o2) -> int {
if (idx == n) return 0;
if (memo[idx][o1][o2] != -1) return memo[idx][o1][o2];
int result = nums[idx] + dfs(idx + 1, o1, o2); // 不执行任何操作
// 只执行操作1
if (o1 > 0) {
int val1 = (nums[idx] + 1) / 2;
result = min(result, val1 + dfs(idx + 1, o1 - 1, o2));
}
// 只执行操作2
if (o2 > 0 && nums[idx] >= k) {
int val2 = nums[idx] - k;
result = min(result, val2 + dfs(idx + 1, o1, o2 - 1));
}
// 先操作1后操作2
if (o1 > 0 && o2 > 0) {
int val1 = (nums[idx] + 1) / 2;
if (val1 >= k) {
int val12 = val1 - k;
result = min(result, val12 + dfs(idx + 1, o1 - 1, o2 - 1));
}
}
// 先操作2后操作1
if (o1 > 0 && o2 > 0 && nums[idx] >= k) {
int val2 = nums[idx] - k;
int val21 = (val2 + 1) / 2;
result = min(result, val21 + dfs(idx + 1, o1 - 1, o2 - 1));
}
return memo[idx][o1][o2] = result;
};
return dfs(0, op1, op2);
}
};
class Solution:
def minArraySum(self, nums: List[int], k: int, op1: int, op2: int) -> int:
n = len(nums)
memo = {}
def dfs(idx, o1, o2):
if idx == n:
return 0
if (idx, o1, o2) in memo:
return memo[(idx, o1, o2)]
result = nums[idx] + dfs(idx + 1, o1, o2) # 不执行任何操作
# 只执行操作1
if o1 > 0:
val1 = (nums[idx] + 1) // 2
result = min(result, val1 + dfs(idx + 1, o1 - 1, o2))
# 只执行操作2
if o2 > 0 and nums[idx] >= k:
val2 = nums[idx] - k
result = min(result, val2 + dfs(idx + 1, o1, o2 - 1))
# 先操作1后操作2
if o1 > 0 and o2 > 0:
val1 = (nums[idx] + 1) // 2
if val1 >= k:
val12 = val1 - k
result = min(result, val12 + dfs(idx + 1, o1 - 1, o2 - 1))
# 先操作2后操作1
if o1 > 0 and o2 > 0 and nums[idx] >= k:
val2 = nums[idx] - k
val21 = (val2 + 1) // 2
result = min(result, val21 + dfs(idx + 1, o1 - 1, o2 - 1))
memo[(idx, o1, o2)] = result
return result
return dfs(0, op1, op2)
public class Solution {
private int[,,] memo;
public int MinArraySum(int[] nums, int k, int op1, int op2) {
int n = nums.Length;
memo = new int[n, op1 + 1, op2 + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= op1; j++) {
for (int l = 0; l <= op2; l++) {
memo[i, j, l] = -1;
}
}
}
return Dfs(nums, k, 0, op1, op2);
}
private int Dfs(int[] nums, int k, int idx, int o1, int o2) {
if (idx == nums.Length) return 0;
if (memo[idx, o1, o2] != -1) return memo[idx, o1, o2];
int result = nums[idx] + Dfs(nums, k, idx + 1, o1, o2); // 不执行任何操作
// 只执行操作1
if (o1 > 0) {
int val1 = (nums[idx] + 1) / 2;
result = Math.Min(result, val1 + Dfs(nums, k, idx + 1, o1 - 1, o2));
}
// 只执行操作2
if (o2 > 0 && nums[idx] >= k) {
int val2 = nums[idx] - k;
result = Math.Min(result, val2 + Dfs(nums, k, idx + 1, o1, o2 - 1));
}
// 先操作1后操作2
if (o1 > 0 && o2 > 0) {
int val1 = (nums[idx] + 1) / 2;
if (val1 >= k) {
int val12 = val1 - k;
result = Math.Min(result, val12 + Dfs(nums, k, idx + 1, o1 - 1, o2 - 1));
}
}
// 先操作2后操作1
if (o1 > 0 && o2 > 0 && nums[idx] >= k) {
int val2 = nums[idx] - k;
int val21 = (val2 + 1) / 2;
result = Math.Min(result, val21 + Dfs(nums, k, idx + 1, o1 - 1, o2 - 1));
}
return memo[idx, o1, o2] = result;
}
}
var minArraySum = function(nums, k, op1, op2) {
const n = nums.length;
const memo = new Map();
function dp(index, remainingOp1, remainingOp2) {
if (index === n) return 0;
const key = `${index},${remainingOp1},${remainingOp2}`;
if (memo.has(key)) return memo.get(key);
const original = nums[index];
let result = Infinity;
// Try all possible combinations of operations for current index
for (let useOp1 = 0; useOp1 <= Math.min(1, remainingOp1); useOp1++) {
for (let useOp2 = 0; useOp2 <= Math.min(1, remainingOp2); useOp2++) {
let value = original;
// Apply operations in both orders to find minimum
if (useOp1 && useOp2) {
// Try op1 first, then op2
let val1 = Math.ceil(original / 2);
if (val1 >= k) val1 -= k;
// Try op2 first, then op1
let val2 = original;
if (val2 >= k) {
val2 -= k;
val2 = Math.ceil(val2 / 2);
}
value = Math.min(val1, val2);
} else if (useOp1) {
value = Math.ceil(value / 2);
} else if (useOp2) {
if (value >= k) value -= k;
}
result = Math.min(result, value + dp(index + 1, remainingOp1 - useOp1, remainingOp2 - useOp2));
}
}
memo.set(key, result);
return result;
}
return dp(0, op1, op2);
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n × op1 × op2)，其中 n 是数组长度。每个状态最多计算一次 |
| 空间复杂度 | O(n × op1 × op2)，记忆化存储的空间复杂度 |