K 次调整数组大小浪费的最小总空间 图解题解

这道题到底在问什么

输入

nums=[10,20,15,30,20], k=2

输出

15 （容量取 [10,20,20,30,30]）

输入

nums=[10,20], k=0

输出

10 （容量全设 20）

先想最直接的笨办法

记牢这套两步走:先用 g 表把任意一段的浪费一次算清,再用 f 表枚举「最后一段切在哪」,把问题拆成前面少一段的子问题。下面先算 g 表,再填 f 表。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢这套两步走:先用 g 表把任意一段的浪费一次算清,再用 f 表枚举「最后一段切在哪」,把问题拆成前面少一段的子问题。下面先算 g 表,再填 f 表。
2. 4先看原始数据 [10,20,15,30,20],它是每个时刻要装的元素数。容量必须盖住元素,盖多了就浪费。如果一段时间用同一个容量,那容量必须等于这段里最大的 nums,多出来的都是浪费。
3. 5先看一个极端:一次都不调整,整条时间线只能用一个容量。那容量得盖住全局最大的 30,五个时刻容量都是 30,总浪费是 30 乘 5 减去元素总和 95,等于 55。这就是不切段的代价。我们要用切段把它压下来。
4. 6搭第一张表 g:行是段的起点 i,列是段的结尾 j。某格 g[i][j] 记的是「把 [i..j] 这段用一个容量装下」的浪费,也就是这段最大值乘段长,再减掉段内元素和。左下角灰掉的「无」是起点比结尾还靠后的非法格。先填对角线。
5. 7对角线上每一格都是「一个数单独成段」。容量正好等于这个数本身,一点不多,浪费全是 0。五个 0 一次填好。接下来往右上方走,看多个数挤在一段会浪费多少。
6. 8g[0][1] 是区间 [10,20] 合成一段。容量得取最大的 20,两个时刻都用 20,总容量 20 乘 2 等于 40,减去这段元素和 30,浪费 10。填进去。
7. 9g[1][2] 是区间 [20,15]。容量取最大的 20,20 乘 2 等于 40,减去和 35,浪费只有 5。这一格待会儿最优解会用到,记一下。
8. 10g[3][4] 是区间 [30,20]。容量取最大的 30,30 乘 2 等于 60,减去和 50,浪费 10。这也是最优解要用的一段,先备着。
9. 11照同样的公式把上三角剩下的格子全补上。比如 [10,20,15,30] 这段最大 30,30 乘 4 减 75 等于 45;整条 [10,20,15,30,20] 最大 30,30 乘 5 减 95 等于 55,正好对上刚才不切段的代价。g 表填满,任意一段的浪费现在都能一眼查到。
10. 12搭第二张表 f:行是「用了前 i 个数」,列是「切成 j 段」。f[i][j] 记这种情况下的最小总浪费。起手只有 f[0][0] 等于 0,意思是零个数零段浪费为零;标「无」的格是数不够分那么多段的非法情况。我们从最左的 1 段列往右填。
11. 13先填 1 段列。只切一段,意味着前 i 个数全挤在一起,浪费就是 g 表里 [0..i-1] 那一段,直接抄过来。一格一格填。
12. 14一段的浪费就是 g 第 0 行原样搬下来:前 1 个数 0,前 2 个 10,前 3 个 15,前 4 个 45,五个全塞一段 55。这一列就是「后面只许一段」的地基,分多段时要靠它接力。
13. 15进入 2 段列。现在允许切两段:枚举最后一段从哪个位置 h 起头,前半段前 h 个数已经在 1 段列算好了,最后一段 [h..i-1] 的浪费从 g 表查。两者相加取最小。前 1 个数分不出两段,标「无」。
14. 16前 2 个数 [10,20] 切两段,只有一种切法:各自一段。f[1][1] 是 0,最后一段 [20] 单独一段浪费也是 0,合起来 0。每个数独占一段,一点不浪费。
15. 17前 3 个数 [10,20,15] 切两段,两个切点都试。切在第 1 个后面:前段 0 加最后一段 [20,15] 浪费 5,得 5;切在第 2 个后面:前段 10 加 [15] 浪费 0,得 10。取小的 5。把 20 和 15 放一段更省。
16. 18前 4 个数 [10,20,15,30] 切两段。逐个切点比下来,最省的是在第 3 个后面切:前段 [10,20,15] 一段浪费 15,最后一段 [30] 浪费 0,合起来 15。把突起的 30 单独拎出来最划算。
17. 19前 5 个数全用上、切两段。最优在第 3 个后面切:前段 [10,20,15] 浪费 15,最后一段 [30,20] 浪费 10,合起来 25。2 段列填满,注意它比 1 段列的 55 已经省了一半多。
18. 20最后一列 3 段,也就是题目要的 k 加 1 段。转移一模一样,只是最后一段前面接的是 2 段列的结果。前 1、前 2 个数不够分 3 段,标「无」。我们要的答案 f[5][3] 就在这一列最底下。
19. 21前 3 个数分 3 段,只能每个数各占一段。前 2 个数分 2 段是 0,最后一段 [15] 浪费 0,合起来 0。三个数各自成段,毫无浪费。
20. 22前 4 个数分 3 段。最省的是在第 3 个后面切:前 3 个数分 2 段是 5,最后一段 [30] 浪费 0,合起来 5。前面把 20、15 凑一段那点浪费,是眼下躲不掉的。
21. 23到正主了:五个数全用上、切成 3 段。逐个枚举最后一段的起点下标 h:从下标 h=2 开始,前段 0 加 [15,30,20] 浪费 25,得 25;从下标 h=3 开始,前段 5 加 [30,20] 浪费 10,得 15;从下标 h=4 开始,前段 15 加 [20] 浪费 0,也是 15。最小是 15。
22. 24取最小值 15 填进 f[5][3]。这就是「五个时刻切成 3 段」的最小总浪费,也就是题目要的答案。两张表都填完了。
23. 25顺着每格当初选的切点回溯:f[5][3] 的最后一段是 [30,20],跳到 f[3][2];f[3][2] 的最后一段是 [20,15],跳到 f[1][1];f[1][1] 就是头一段 [10]。三段正好是 [10]、[20,15]、[30,20]。
24. 26回到原数组看最终分法:绿色 [10] 一段容量 10,蓝色 [20,15] 一段容量 20,红色 [30,20] 一段容量 30。五个时刻容量排成 [10,20,20,30,30],浪费只在下标 2 多 5、下标 4 多 10,一共 15,和表算出的严丝合缝。突起的大值各自靠后成段,是最省的切法。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        k += 1
        n = len(nums)
        g = [[0] * n for _ in range(n)]
        for i in range(n):
            s = mx = 0
            for j in range(i, n):
                s += nums[j]
                mx = max(mx, nums[j])
                g[i][j] = mx * (j - i + 1) - s
        f = [[inf] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, k + 1):
                for h in range(i):
                    f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
        return f[-1][-1]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        ++k;
        int n = nums.size();
        vector<vector<int>> g(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            int s = 0, mx = 0;
            for (int j = i; j < n; ++j) {
                mx = max(mx, nums[j]);
                s += nums[j];
                g[i][j] = mx * (j - i + 1) - s;
            }
        }
        int inf = 0x3f3f3f3f;
        vector<vector<int>> f(n + 1, vector<int>(k + 1, inf));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                for (int h = 0; h < i; ++h) {
                    f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]);
                }
            }
        }
        return f[n][k];
    }
};

import java.util.*;
class Solution {
    public int minSpaceWastedKResizing(int[] nums, int k) {
        ++k;
        int n = nums.length;
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++i) {
            int s = 0, mx = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                mx = Math.max(mx, nums[j]);
                g[i][j] = mx * (j - i + 1) - s;
            }
        }
        int[][] f = new int[n + 1][k + 1];
        int inf = 0x3f3f3f3f;
        for (int i = 0; i < f.length; ++i) {
            Arrays.fill(f[i], inf);
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                for (int h = 0; h < i; ++h) {
                    f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]);
                }
            }
        }
        return f[n][k];
    }
}

复杂度

面试官可能追问