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

容量能改 k 次，浪费到底怎么算？

nums[t] 是第 t 个时刻（下标从 0 数起）要装的元素数，容量不能小于它，多出的就是浪费；最多调 k 次，初始设定不计入，求总浪费最小。题面例子 nums=[10,20,15,30,20] 最多调 2 次，答案 15。

两次调整之间容量不变，调 k 次等于把时间轴切成 k+1 段。

把每种切法都试一遍，账要算多大？

n 个时刻有 n-1 个空隙，切成 k+1 段的方案数是 C(n-1,k)（从 n-1 个空隙里挑 k 个的选法数），n=200 时有几十位，试不完。

重复也躲不掉：不同切法常共用前缀，同一笔账算了又算。这笔账只由前缀决定，存下来复用——这就是动态规划（简称 DP，把「前 i 个时刻切 j 段的最小浪费」记进表、后面直接取）。

一段的容量为什么必须取段内最大值？

一段之内容量不动、又得每刻盖得住，只能取段内最大的 nums，再大只多浪费。这段浪费于是定死：最大值乘段长，减段内元素和。

开一张 g 表：g[i][j] 存 [i..j] 这段的浪费；固定起点 i、右挪结尾 j，顺手维护最大值与和，每格 O(1) 填出（大 O 记号，描述规模变大时操作次数怎么涨）。

最后一段切在哪，凭什么拆成子问题？

这是划分 DP——把一排东西切成几段、逐段结账。定义 f[i][j]：前 i 个时刻切成 j 段的最小总浪费。最后一段总从某个下标 h 到 i-1，代价 g[h][i-1]；砍掉它，剩下正是「前 h 个时刻切 j-1 段」。

转移（由小问题推这一格的式子）：对每个 h 取 f[h][j-1]+g[h][i-1] 的最小值。f[0][0]=0 是 base case（最简单、不用再拆的情况），其余铺无穷大当暂无方案。答案在 f[n][k+1]。

[10,20,15,30,20]调 2 次，15 是怎么切出来的

先填 g：对角线单独成段全 0；g[0][1]=20×2-30=10，g[1][2]=5，g[2][3]=15，g[3][4]=10，g[0][2]=15，g[2][4]=25，g[0][3]=45，g[0][4]=55。

再填 f，段数 3。1 段列抄 g 第 0 行：0、10、15、45、55。2 段列：f[3][2]=min(0+5,10+0)=5，f[4][2]=min(0+25,10+15,15+0)=15，f[5][2]=min(0+35,10+25,15+10,45+0)=25。3 段列：f[3][3]=0、f[4][3]=5；f[5][3] 的最后一段从下标 2、3、4 起，各给 0+25=25（f[2][2]=g[1][1] 一段自身=0）、5+10=15、15+0=15，取 15 即题面答案。

忘了把 k 加 1，15 为什么会算成 25？

段数是 k+1 不是 k；拿 k 当段数，本例只切 2 段，答案停在 f[5][2]=25。k 取 0 时只许一段、容量取全局最大。f 的初值铺 0 而不是无穷大，会让数不够分段的非法格混进最小值。

g 表 O(n²)，f 表 n×(k+1) 格、每格枚举 O(n) 起点，时间 O(n²·k)，空间 O(n²+n·k)。

Python

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]

C++

#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];
    }
};

Java

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];
    }
}