拆分数组的最小代价

题目

2547. 拆分数组的最小代价

---

给你一个整数数组 nums 和一个整数 k 。

将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。

令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。

• 例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。

子数组的 重要性 定义为 k + trimmed(subarray).length 。

• 例如，如果一个子数组是 [1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。

找出并返回拆分 nums 的所有可行方案中的最小代价。

子数组 是数组的一个连续 非空 元素序列。

示例 1：

输入：nums = [1,2,1,2,1,3,3], k = 2
输出：8
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3]
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。
拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 2：

输入：nums = [1,2,1,2,1], k = 2
输出：6
解释：将 nums 拆分成两个子数组：[1,2], [1,2,1] 。
[1,2] 的重要性是 2 + (0) = 2 。
[1,2,1] 的重要性是 2 + (2) = 4 。
拆分的代价是 2 + 4 = 6 ，可以证明这是所有可行的拆分方案中的最小代价。

示例 3：

输入：nums = [1,2,1,2,1], k = 5
输出：10
解释：将 nums 拆分成一个子数组：[1,2,1,2,1].
[1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。
拆分的代价是 10 ，可以证明这是所有可行的拆分方案中的最小代价。

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < nums.length
• 1 <= k <= 10^9

题解

方法一：

思路

不妨设$f_i$为前i个数的最小代价。
初始化$f_0 = 0, f_i = INF, i>0$

$f_i = min(f_i, f_j+k+trimmed(nums_{j+1,\dots, i}).length), 0\le j\le i$

代码

class Solution {
public:
    using ll = long long;
    ll f[1005];
    int minCost(vector<int>& nums, int k) {
        memset(f, 0x3f, sizeof(f));
        int n = nums.size();
        f[0] = 0;
        for (int i=1; i<=n; i++) {
            int cnt = 0;
            vector<int> mp(n);
            for (int j=i; j>0; j--) {
                mp[nums[j-1]]++;
                if (mp[nums[j-1]] == 1) cnt++;
                else if (mp[nums[j-1]] == 2) cnt--;
                f[i] = min(f[i], f[j-1]+i-j+1-cnt+k);
            }
        }
        return f[n];
    }
};