题目描述
思路解析动画文字版
记牢这套两步走:先用 g 表把任意一段的浪费一次算清,再用 f 表枚举「最后一段切在哪」,把问题拆成前面少一段的子问题。下面先算 g 表,再填 f 表。
先看原始数据 [10,20,15,30,20],它是每个时刻要装的元素数。容量必须盖住元素,盖多了就浪费。如果一段时间用同一个容量,那容量必须等于这段里最大的 nums,多出来的都是浪费。
先看一个极端:一次都不调整,整条时间线只能用一个容量。那容量得盖住全局最大的 30,五个时刻容量都是 30,总浪费是 30 乘 5 减去元素总和 95,等于 55。这就是不切段的代价。我们要用切段把它压下来。
搭第一张表 g:行是段的起点 i,列是段的结尾 j。某格 g[i][j] 记的是「把 [i..j] 这段用一个容量装下」的浪费,也就是这段最大值乘段长,再减掉段内元素和。左下角灰掉的「无」是起点比结尾还靠后的非法格。先填对角线。
对角线上每一格都是「一个数单独成段」。容量正好等于这个数本身,一点不多,浪费全是 0。五个 0 一次填好。接下来往右上方走,看多个数挤在一段会浪费多少。
g[0][1] 是区间 [10,20] 合成一段。容量得取最大的 20,两个时刻都用 20,总容量 20 乘 2 等于 40,减去这段元素和 30,浪费 10。填进去。
g[1][2] 是区间 [20,15]。容量取最大的 20,20 乘 2 等于 40,减去和 35,浪费只有 5。这一格待会儿最优解会用到,记一下。
g[3][4] 是区间 [30,20]。容量取最大的 30,30 乘 2 等于 60,减去和 50,浪费 10。这也是最优解要用的一段,先备着。
照同样的公式把上三角剩下的格子全补上。比如 [10,20,15,30] 这段最大 30,30 乘 4 减 75 等于 45;整条 [10,20,15,30,20] 最大 30,30 乘 5 减 95 等于 55,正好对上刚才不切段的代价。g 表填满,任意一段的浪费现在都能一眼查到。
搭第二张表 f:行是「用了前 i 个数」,列是「切成 j 段」。f[i][j] 记这种情况下的最小总浪费。起手只有 f[0][0] 等于 0,意思是零个数零段浪费为零;标「无」的格是数不够分那么多段的非法情况。我们从最左的 1 段列往右填。
先填 1 段列。只切一段,意味着前 i 个数全挤在一起,浪费就是 g 表里 [0..i-1] 那一段,直接抄过来。一格一格填。
一段的浪费就是 g 第 0 行原样搬下来:前 1 个数 0,前 2 个 10,前 3 个 15,前 4 个 45,五个全塞一段 55。这一列就是「后面只许一段」的地基,分多段时要靠它接力。
进入 2 段列。现在允许切两段:枚举最后一段从哪个位置 h 起头,前半段前 h 个数已经在 1 段列算好了,最后一段 [h..i-1] 的浪费从 g 表查。两者相加取最小。前 1 个数分不出两段,标「无」。
前 2 个数 [10,20] 切两段,只有一种切法:各自一段。f[1][1] 是 0,最后一段 [20] 单独一段浪费也是 0,合起来 0。每个数独占一段,一点不浪费。
前 3 个数 [10,20,15] 切两段,两个切点都试。切在第 1 个后面:前段 0 加最后一段 [20,15] 浪费 5,得 5;切在第 2 个后面:前段 10 加 [15] 浪费 0,得 10。取小的 5。把 20 和 15 放一段更省。
前 4 个数 [10,20,15,30] 切两段。逐个切点比下来,最省的是在第 3 个后面切:前段 [10,20,15] 一段浪费 15,最后一段 [30] 浪费 0,合起来 15。把突起的 30 单独拎出来最划算。
前 5 个数全用上、切两段。最优在第 3 个后面切:前段 [10,20,15] 浪费 15,最后一段 [30,20] 浪费 10,合起来 25。2 段列填满,注意它比 1 段列的 55 已经省了一半多。
最后一列 3 段,也就是题目要的 k 加 1 段。转移一模一样,只是最后一段前面接的是 2 段列的结果。前 1、前 2 个数不够分 3 段,标「无」。我们要的答案 f[5][3] 就在这一列最底下。
前 3 个数分 3 段,只能每个数各占一段。前 2 个数分 2 段是 0,最后一段 [15] 浪费 0,合起来 0。三个数各自成段,毫无浪费。
前 4 个数分 3 段。最省的是在第 3 个后面切:前 3 个数分 2 段是 5,最后一段 [30] 浪费 0,合起来 5。前面把 20、15 凑一段那点浪费,是眼下躲不掉的。
到正主了:五个数全用上、切成 3 段。逐个枚举最后一段的起点下标 h:从下标 h=2 开始,前段 0 加 [15,30,20] 浪费 25,得 25;从下标 h=3 开始,前段 5 加 [30,20] 浪费 10,得 15;从下标 h=4 开始,前段 15 加 [20] 浪费 0,也是 15。最小是 15。
取最小值 15 填进 f[5][3]。这就是「五个时刻切成 3 段」的最小总浪费,也就是题目要的答案。两张表都填完了。
顺着每格当初选的切点回溯: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]。
回到原数组看最终分法:绿色 [10] 一段容量 10,蓝色 [20,15] 一段容量 20,红色 [30,20] 一段容量 30。五个时刻容量排成 [10,20,20,30,30],浪费只在下标 2 多 5、下标 4 多 10,一共 15,和表算出的严丝合缝。突起的大值各自靠后成段,是最省的切法。
边界想清:k=0 只能整条一段、容量取全局最大;每段值相等时零浪费;段数够多时把每个突起单独切出来最省。
面试重点:讲清区间划分 DP 的最优子结构、g 表预处理换掉重复计算、复杂度 O(n 平方乘 k)。
参考代码
from __future__ import annotationsfrom 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]复杂度
- 时间：O(n² · k)，预处理 g 表是 O(n²);填 f 表状态有 n 乘 k 个,每个状态再枚举最后一段起点 O(n),合起来 O(n² 乘 k),k 这里指 k 加 1 段
- 空间：O(n² + n · k)，按峰值算:g 表占 n 乘 n,f 表占 n 乘 k。都是二维表,不随规模平方叠加,峰值就是两张表之和
易错点
面试追问把动画讲成自己的话
追问为什么这题是 DP,不能贪心地每次挑浪费最大的地方切一刀?
追问段浪费表 g 有必要预处理吗,能不能边填 f 边算?
追问复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
两个回文子序列长度的最大乘积
LeetCode 2002 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题