Kimi LeetCode 2547. 拆分数组的最小代价 C++实现

这道题的核心思路是动态规划 记忆化搜索。我们定义 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 实现cppclass Solution {public:int minCost(vectorint nums, int k) {int n nums.size();// f[i] 表示从下标 i 开始拆分的最小代价0 表示未计算// 注意题目保证答案为正所以可以用 0 作为未访问标记vectorint f(n, 0);functionint(int) dfs [](int i) - int {if (i n) return 0;if (f[i] ! 0) return f[i];// cnt[x] 记录子数组中数字 x 的出现次数// 由于 nums[i] n可以用数组代替哈希表vectorint 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 长度 - oneint 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) 21 和 2 都只出现一次trimmed 后长度为 0- 第二个子数组2 (5 - 3) 61 出现 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 开源社区 。