这道题的核心思路是动态规划 + 记忆化搜索。我们定义 `dfs(i)` 为从下标 `i` 开始拆分数组的最小代价，答案即为 `dfs(0)`。
关键观察
子数组的重要性 = `k + trimmed(subarray).length`。其中 `trimmed` 操作会移除子数组中只出现一次的数字。
如果我们用 `cnt[x]` 记录数字 `x` 在当前子数组中的出现次数，用 `one` 记录出现次数恰好为 1 的数字个数，那么：
- `trimmed(subarray).length = 子数组总长度 - one`
- 重要性 = `k + (j - i + 1) - one`
算法设计
在 `dfs(i)` 中，枚举子数组的右端点 `j`（从 `i` 到 `n-1`），同时维护一个计数数组和 `one` 变量：
- 当 `nums[j]` 第一次出现时，`one++`
- 当 `nums[j]` 第二次出现时，它从"唯一"变成"重复"，所以 `one--`
- 第三次及以上出现，`one` 不变
转移方程：
```
dfs(i) = min{ k + (j - i + 1 - one) + dfs(j + 1) } 对所有 j ≥ i
```
使用记忆化数组 `f[i]` 避免重复计算。
C++ 实现
```cpp
class Solution {
public:
int minCost(vector<int>& nums, int k) {
int n = nums.size();
// f[i] 表示从下标 i 开始拆分的最小代价，0 表示未计算
// 注意：题目保证答案为正，所以可以用 0 作为未访问标记
vector<int> f(n, 0);
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (f[i] != 0) return f[i];
// cnt[x] 记录子数组中数字 x 的出现次数
// 由于 nums[i] < n，可以用数组代替哈希表
vector<int> cnt(n, 0);
int one = 0; // 出现次数为 1 的数字个数
int ans = INT_MAX;
for (int j = i; j < n; ++j) {
int x = ++cnt[nums[j]];
if (x == 1) {
++one; // 新出现的唯一数字
} else if (x == 2) {
--one; // 从唯一变成重复
}
// x >= 3 时，one 不变（已经是重复数字）
// 当前子数组 [i, j] 的重要性：k + 长度 - one
int cost = k + (j - i + 1 - one) + dfs(j + 1);
ans = min(ans, cost);
}
f[i] = ans;
return ans;
};
return dfs(0);
}
};
```
复杂度分析
- 时间复杂度：O(n^2)。每个状态 `dfs(i)` 最多计算一次，每次计算需要 O(n) 的枚举。
- 空间复杂度：O(n)。记忆化数组和递归栈的空间。
示例验证
以 `nums = [1,2,1,2,1,3,3], k = 2` 为例：
- 拆分为 `[1,2]` 和 `[1,2,1,3,3]`
- 第一个子数组：2 + (2 - 2) = 2（1 和 2 都只出现一次，trimmed 后长度为 0）
- 第二个子数组：2 + (5 - 3) = 6（1 出现 3 次，2 出现 1 次，3 出现 2 次；仅出现一次的是 2，所以 trimmed 长度为 4？不对，重新算：1 出现 3 次保留，2 出现 1 次移除，3 出现 2 次保留，trimmed = [1,1,3,3]，长度为 4，重要性 = 2 + 4 = 6）
- 总代价 = 2 + 6 = 8 ✓
参考实现来自 LeetCode 官方题解和 Doocs 开源社区 。
