2547. 拆分数组的最小代价

发表于 分类于 阅读次数： Waline： 本文字数： 107 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

划分DP的裸题，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int minCost(vector<int>& nums, int k) {
    int n = nums.size();
    int f[1005];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int cnt[1005];
      memset(cnt, 0, sizeof(cnt));
      int s = 0;
      for (int j = i; j >= 1; --j) {
        if (cnt[nums[j - 1]] >= 2) s -= cnt[nums[j - 1]];
        cnt[nums[j - 1]]++;
        if (cnt[nums[j - 1]] >= 2) s += cnt[nums[j - 1]];
        f[i] = min(f[i], f[j - 1] + s + k);
      }
    }
    return f[n];
  }
};