Medium
题目描述
给你一个整数数组 nums。你的任务是通过执行以下操作之一来移除数组中的所有元素，直到 nums 为空：
- 从
nums的前三个元素中选择任意两个元素并将它们移除。此操作的代价是被移除的两个元素中的最大值。 - 如果
nums中剩余的元素少于三个，则在一次操作中移除所有剩余元素。此操作的代价是剩余元素中的最大值。
返回移除所有元素所需的最小代价。
示例 1：
输入：nums = [6,2,8,4]
输出：12
解释：
初始时，nums = [6, 2, 8, 4]。
- 第一次操作中，移除 nums[0] = 6 和 nums[2] = 8，代价为 max(6, 8) = 8。现在 nums = [2, 4]。
- 第二次操作中，移除剩余元素，代价为 max(2, 4) = 4。
移除所有元素的总代价为 8 + 4 = 12。这是移除 nums 中所有元素的最小代价，因此输出为 12。
示例 2：
输入：nums = [2,1,3,3]
输出：5
解释：
初始时，nums = [2, 1, 3, 3]。
- 第一次操作中，移除 nums[0] = 2 和 nums[1] = 1，代价为 max(2, 1) = 2。现在 nums = [3, 3]。
- 第二次操作中，移除剩余元素，代价为 max(3, 3) = 3。
移除所有元素的总代价为 2 + 3 = 5。这是移除 nums 中所有元素的最小代价，因此输出为 5。
约束条件：
1 <= nums.length <= 10001 <= nums[i] <= 10^6
解题思路
这道题需要用动态规划来解决。关键观察是每次操作后，剩余的元素都形成原数组的一个前缀。
思路分析：
我们定义状态 dp[i][j] 表示在数组的前 i 个元素中，最后剩余元素为 nums[j] 时的最小代价。
状态转移的关键在于理解操作的本质：
- 当我们从前三个元素中选择两个移除时，实际上是在决定哪个元素保留
- 保留的元素会成为新数组的第一个元素
- 移除操作的代价是被移除两个元素的最大值
对于状态转移：
- 当
i < 3时，我们只能移除所有剩余元素，代价是剩余元素的最大值 - 当
i >= 3时，我们可以选择从前三个元素中移除两个，保留一个作为新的起始元素
具体来说，如果我们要计算 dp[i][j]（最后剩余元素为 nums[j]），我们需要考虑：
- 如果
j在前三个位置中，我们可以选择移除其他两个元素 - 递归地计算之前状态的最小代价
最终答案就是所有可能的最后剩余元素对应的最小代价。
代码实现
class Solution {
public:
int minCost(vector<int>& nums) {
int n = nums.size();
if (n <= 2) {
return *max_element(nums.begin(), nums.end());
}
vector<vector<int>> dp(n + 1, vector<int>(n, INT_MAX));
// 初始化：如果只剩1-2个元素，代价就是最大值
for (int i = 0; i < min(3, n); i++) {
int maxVal = 0;
for (int k = 0; k <= i; k++) {
maxVal = max(maxVal, nums[k]);
}
dp[i + 1][i] = maxVal;
}
// 动态规划
for (int i = 3; i < n; i++) {
for (int j = 0; j < 3; j++) {
// 保留第j个元素，移除其他两个
int cost = 0;
for (int k = 0; k < 3; k++) {
if (k != j) {
cost = max(cost, nums[k]);
}
}
for (int prev = j; prev < i - 2; prev++) {
if (dp[i - 2][prev] != INT_MAX) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i - 2][prev] + cost);
}
}
}
// 更新数组，移除前两个元素
for (int k = 0; k < n - 2; k++) {
nums[k] = nums[k + 2];
}
i -= 2;
n -= 2;
}
int result = INT_MAX;
for (int j = 0; j < n; j++) {
result = min(result, dp[n][j]);
}
return result;
}
};
class Solution:
def minCost(self, nums: List[int]) -> int:
n = len(nums)
memo = {}
def dp(arr):
if len(arr) <= 2:
return max(arr) if arr else 0
arr_tuple = tuple(arr)
if arr_tuple in memo:
return memo[arr_tuple]
result = float('inf')
# 尝试从前三个元素中选择两个移除
for i in range(3):
for j in range(i + 1, 3):
if i < len(arr) and j < len(arr):
# 移除第i个和第j个元素
cost = max(arr[i], arr[j])
new_arr = [arr[k] for k in range(len(arr)) if k != i and k != j]
result = min(result, cost + dp(new_arr))
memo[arr_tuple] = result
return result
return dp(nums)
public class Solution {
private Dictionary<string, int> memo = new Dictionary<string, int>();
public int MinCost(int[] nums) {
return DP(nums.ToList());
}
private int DP(List<int> arr) {
if (arr.Count <= 2) {
return arr.Count == 0 ? 0 : arr.Max();
}
string key = string.Join(",", arr);
if (memo.ContainsKey(key)) {
return memo[key];
}
int result = int.MaxValue;
// 尝试从前三个元素中选择两个移除
for (int i = 0; i < Math.Min(3, arr.Count); i++) {
for (int j = i + 1; j < Math.Min(3, arr.Count); j++) {
int cost = Math.Max(arr[i], arr[j]);
List<int> newArr = new List<int>();
for (int k = 0; k < arr.Count; k++) {
if (k != i && k != j) {
newArr.Add(arr[k]);
}
}
result = Math.Min(result, cost + DP(newArr));
}
}
memo[key] = result;
return result;
}
}
var minCost = function(nums) {
const memo = new Map();
function dp(arr) {
if (arr.length <= 2) {
return arr.length === 0 ? 0 : Math.max(...arr);
}
const key = arr.join(',');
if (memo.has(key)) {
return memo.get(key);
}
let minCost = Infinity;
// Try all combinations of removing 2 elements from first 3
for (let i = 0; i < Math.min(3, arr.length); i++) {
for (let j = i + 1; j < Math.min(3, arr.length); j++) {
const cost = Math.max(arr[i], arr[j]);
const newArr = arr.filter((_, idx) => idx !== i && idx !== j);
minCost = Math.min(minCost, cost + dp(newArr));
}
}
memo.set(key, minCost);
return minCost;
}
return dp(nums);
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(3^n) |
| 空间复杂度 | O(3^n) |
注：由于每次操作最多有3种选择方式（从前3个元素中选2个），递归深度最多为n，所以时间复杂度为O(3^n)。空间复杂度主要来自于记忆化存储和递归调用栈。