title
给你一个整数数组 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 <= 10000 <= nums[i] < nums.length1 <= k <= 109
solution
一维DP。
dp(i)表示以0…i的代价，求dp(n-1)。
用map维护出现不止一次的元素个数。
INF = int(1e20)
class Solution:
def minCost(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [INF for _ in range(n)]
for i in range(n):
res = INF
cnt = collections.Counter()
t = 0
for j in range(i, -1, -1):
cnt[nums[j]] += 1
if cnt[nums[j]] == 2:
t += 2
elif cnt[nums[j]] > 2:
t += 1
res = min(res, (dp[j - 1] if j - 1 >= 0 else 0) + k + t)
# if i == n-1 and j == 2:
# print("x")
dp[i] = res
# print(dp)
return dp[n - 1]