这道题是典型的区间DP（动态规划）问题，核心在于如何高效计算每个子数组的"重要性"。
问题分析
重要性的计算规则：
- 子数组中只出现一次的数字会被移除（不计入长度）
- 重要性 = k + 剩余数字的个数
- 等价于：重要性 = k + (子数组长度 - 只出现一次的数字个数)
关键观察：
- 某个数字在子数组中出现1次 → 不贡献长度
- 出现2次及以上 → 全部贡献长度（包括第1次）
动态规划思路
定义 dp[i] 表示拆分前 i 个元素（下标 0 到 i-1）的最小代价。
状态转移：
dp[i] = min(dp[j] + cost(j, i-1)) 其中 0 ≤ j < i
- dp[0] = 0（空数组代价为0）
- cost(l, r) 表示子数组 nums[l..r] 的重要性
Java实现
class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n + 1];
// 初始化dp数组为较大值
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
// 枚举每个结束位置
for (int i = 1; i <= n; i++) {
// 统计当前子数组中每个数字的出现次数
int[] count = new int[n]; // nums[i] < nums.length
int uniqueCount = 0; // 只出现一次的数字个数
// 从后往前枚举子数组起点
for (int j = i - 1; j >= 0; j--) {
int val = nums[j];
count[val]++;
if (count[val] == 1) {
// 首次出现，算作"唯一"数字
uniqueCount++;
} else if (count[val] == 2) {
// 第二次出现，不再唯一
uniqueCount--;
}
// 出现3次及以上，不影响uniqueCount
// 子数组长度 = i - j
int subLen = i - j;
// 重要性 = k + (子数组长度 - 唯一数字个数)
int importance = k + (subLen - uniqueCount);
// 更新dp[i]
dp[i] = Math.min(dp[i], dp[j] + importance);
}
}
return dp[n];
}
}
代码优化（使用HashMap处理任意数值范围）
如果 nums[i] 的范围不固定，可以用 HashMap 替代数组：
class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
Map<Integer, Integer> freq = new HashMap<>();
int uniqueCount = 0;
for (int j = i - 1; j >= 0; j--) {
int val = nums[j];
int count = freq.getOrDefault(val, 0) + 1;
freq.put(val, count);
if (count == 1) {
uniqueCount++;
} else if (count == 2) {
uniqueCount--;
}
int subLen = i - j;
int importance = k + (subLen - uniqueCount);
dp[i] = Math.min(dp[i], dp[j] + importance);
}
}
return dp[n];
}
}
复杂度分析
- 时间复杂度：O(n²)，n ≤ 1000，完全可行
- 空间复杂度：O(n)
示例验证
以 nums = [1,2,1,2,1,3,3], k = 2 为例：
- 最优拆分：[1,2] + [1,2,1,3,3]
- 代价 = (2 + 0) + (2 + 4) = 8 ✅
这个解法清晰高效，能通过LeetCode的所有测试用例。′
