1959. K 次调整数组大小浪费的最小总空间

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

考点

  • 划分DP

思路

题意是，数组最多划分k + 1个子数组，每个子数组的开销为： \[ \text{cost}(i,j) = \max_{t\in[i,j]} nums[t]\cdot (j-i+1) - \sum_{t=i}^j nums[t] \] 求子数组开销和的最小值

之所以可以这么认为，是因为就算两个区间的最大值一样，按题意应该合并成一个区间的；

可不论合并与否，这两个数组转换为区间最大值的开销并没有改变，即不会对答案造成任何影响

AC代码：

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

滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  const int inf = 0x3f3f3f3f;
  int minSpaceWastedKResizing(vector<int>& nums, int k) {
    k++;
    int f[2][205], n = nums.size();
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int j = 1; j <= k; ++j) {
      for (int r = j; r <= n; ++r) {
        int mx = -1, s = 0;
        f[j & 1][r] = inf;
        for (int l = r; l >= j; --l) {
          s += nums[l - 1], mx = max(mx, nums[l - 1]);
          f[j & 1][r] =
              min(f[j & 1][r], f[j - 1 & 1][l - 1] + (r - l + 1) * mx - s);
        }
      }
    }
    return f[k & 1][n];
  }
};