这道题的核心思路是动态规划 + 记忆化搜索。我们定义 `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 开源社区 。