这道题是典型的区间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的所有测试用例。′