拆分数组的最小代价
难度:
标签:
题目描述
You are given an integer array nums and an integer k.
Split the array into some number of non-empty subarrays. The cost of a split is the sum of the importance value of each subarray in the split.
Let trimmed(subarray) be the version of the subarray where all numbers which appear only once are removed.
- For example,
trimmed([3,1,2,4,3,4]) = [3,4,3,4].
The importance value of a subarray is k + trimmed(subarray).length.
- For example, if a subarray is
[1,2,3,3,3,4,4], then trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4].The importance value of this subarray will bek + 5.
Return the minimum possible cost of a split of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,1,2,1,3,3], k = 2 Output: 8 Explanation: We split nums to have two subarrays: [1,2], [1,2,1,3,3]. The importance value of [1,2] is 2 + (0) = 2. The importance value of [1,2,1,3,3] is 2 + (2 + 2) = 6. The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits.
Example 2:
Input: nums = [1,2,1,2,1], k = 2 Output: 6 Explanation: We split nums to have two subarrays: [1,2], [1,2,1]. The importance value of [1,2] is 2 + (0) = 2. The importance value of [1,2,1] is 2 + (2) = 4. The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits.
Example 3:
Input: nums = [1,2,1,2,1], k = 5 Output: 10 Explanation: We split nums to have one subarray: [1,2,1,2,1]. The importance value of [1,2,1,2,1] is 5 + (3 + 2) = 10. The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits.
Constraints:
1 <= nums.length <= 10000 <= nums[i] < nums.length1 <= k <= 109
代码结果
运行时间: 332 ms, 内存: 18.3 MB
/*
* 思路：
* 1. 使用动态规划来解决问题。
* 2. dp[i]表示将nums的前i个元素拆分的最小代价。
* 3. 使用一个哈希图来计算trimmed子数组的重要性。
* 4. 遍历每一个可能的拆分点，计算并更新dp数组。
* 5. 使用Java Stream API来简化部分计算。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
Map<Integer, Long> countMap = new HashMap<>();
int[] trimmedLength = {0};
List<Integer> sublist = Arrays.stream(nums, 0, i).boxed().collect(Collectors.toList());
for (int j = i; j > 0; j--) {
int num = sublist.get(j - 1);
countMap.put(num, countMap.getOrDefault(num, 0L) + 1);
if (countMap.get(num) == 2) {
trimmedLength[0] += 2;
} else if (countMap.get(num) > 2) {
trimmedLength[0] += 1;
}
dp[i] = Math.min(dp[i], dp[j - 1] + k + trimmedLength[0]);
}
}
return dp[n];
}
}解释
方法:
这个题解使用了线段树来优化动态规划的过程。具体思路如下：
1. 定义状态 f[i] 表示将数组 nums[:i] 拆分成若干个非空子数组的最小代价。
2. 状态转移时，对于每个 i，枚举上一个拆分点 j，计算 [j+1,i] 这一段的重要性，加上 f[j] 作为一种拆分方案，取所有方案的最小值作为 f[i] 的值。
3. 朴素的状态转移复杂度为 O(n^2)，因此使用线段树优化，将每次查询 f[j] 的最小值的复杂度降至 O(log n)。
4. 线段树中维护区间加的懒标记，同时在更新答案时，需要对每个数字 x 维护其出现的上一个位置和上上个位置，方便线段树对区间进行修改。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在解法中，如何通过线段树优化动态规划的查询和更新操作？具体是如何实现的？
▷🦆
为什么在更新线段树时，需要维护数字的上一个位置和上上个位置？这与算法的哪一部分逻辑直接相关？
▷🦆
在实现线段树时，为什么选择使用懒惰传播（lazy propagation）？这种方法在本题中有什么特别的优势？
▷