题目描述
思路解析
一句话答案：LeetCode 1547 切棍子的最小成本用区间 DP：每刀成本=当刀那段的长度，0 和 n 也当端点，dp[i][j]=切开这段的最少花费，枚举第一刀取小：dp[i][k]+dp[k][j]+段长，时间 O(c³)、空间 O(c²)。
一根木棍随便切，为什么顺序不同总价会差这么多
给一根长度 n 的木棍和切点清单 cuts，要把这些位置全切开。每刀成本等于当刀那段此刻的长度，切的先后自己定，求总成本的最小值。n=7、cuts=[1,3,4,5] 时答案 16。先切中间早断成短段、后面每刀便宜，先切两端则长段拖到最后反复付大数——难点全在顺序。
把所有切割顺序都试一遍，为什么棍子稍长就试不完
c 个切点排先后共 c! 种，c 才十几就多到枚举不完。且里面全是重复：剩下同一段、夹着同一批没切的点，往后最小成本就一样，却被反复重算。把『某段内部全切开』这个子问题算一次、存下来复用，就是动态规划（简称 DP）省浪费的办法。
把 0 和 n 也算成端点，dp[i][j] 到底存的是什么
把两端 0 和 n 也塞进切点，连同 cuts 排序，得端点数组 arr，本例 arr=[0,1,3,4,5,7] 共 6 个端点，任何一段都能用一对端点框出来。状态定成 dp[i][j]（i、j 是 arr 下标，i 左 j 右，从 0 数起）：切开 arr[i] 到 arr[j] 之间所有切点最少花多少。相邻端点间没夹切点，dp 值为 0；答案是整根的 dp[0][5]。『状态是一段区间、从短到长填表』的做法叫区间 DP。
为什么枚举『第一刀先切哪』，两段子成本一加就对了
填 dp[i][j] 只盯这段上『第一刀』先切哪个点。第一刀落下时整段还完整连着，必付一次段长 arr[j]-arr[i]，与选哪个点无关。第一刀一落，整段劈成两截，各自内部正好是两个更小的子问题 dp[i][k] 和 dp[k][j]，于是选点 k（k 取 i、j 之间的切点下标，i<k<j）的总成本是 dp[i][k]+dp[k][j]+(arr[j]-arr[i])。取遍候选 k 求最小，这就是转移式（由子区间成本推出这段成本）。
拿 n=7 的示例把三角表填到 16
相邻端点没夹切点的格填 0，再从短区间往长填。跨度 2（中间只夹 1 个切点）只有一个候选：dp[0][2]=0+0+(3-0)=3，dp[1][3]=3，dp[2][4]=2，dp[3][5]=3。跨度 3 试两候选取小：dp[0][3] 两个候选 0+3+4 与 3+0+4 都得 7；dp[1][4] 切 arr[2] 得 0+2+4=6；dp[2][5]=2+0+4=6。跨度 4：dp[0][4] 三候选 11、10、12 取 10；dp[1][5] 三候选都是 12。整根 dp[0][5] 段长 7：切 arr[1] 得 0+12+7=19、切 arr[2] 得 3+6+7=16、切 arr[3] 和 arr[4] 都得 17，最小 16 即答案。
段长若跟着第一刀一起变，dp 为什么会算出一堆虚高成本
常见写歪点是让段长随第一刀变——可第一刀切的是还没断开的整段，段长只认两端，让它随切点变，每个候选都加错数，整张表一路歪。边界：只有一个切点时成本恒等于整根长度，如 n=2、cuts=[1] 一刀就是 2。复杂度：枚举区间 O(c²)，每区间再枚举第一刀 O(c)，合计时间 O(c³)（大 O 记号，描述规模变大时操作数怎么涨），空间 O(c²)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。
先看表骨架:行列都对应排序后的端点 arr=[0, 1, 3, 4, 5, 7]。dp[i][j] 是「切开 arr[i] 到 arr[j] 之间所有切点」的最小成本。对角线、下方,以及相邻端点(j 比 i 大 1)这些格子里都没有内部切点,成本 0,已经直接填好;只有上三角里跨度更大的「·」还没算,我们从最短的区间开始填。
轮到 dp[0][2](紫格)。这段棍子从 0 到 3,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][2]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
候选 3 刷新了最优,暂定 dp[0][2]=3,对应「第一刀先切 arr[1]=1」。
区间内所有候选 k 试完,dp[0][2]=3 锁定(变绿)。它代表把 0..3 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[1][3](紫格)。这段棍子从 1 到 4,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
候选 3 刷新了最优,暂定 dp[1][3]=3,对应「第一刀先切 arr[2]=3」。
区间内所有候选 k 试完,dp[1][3]=3 锁定(变绿)。它代表把 1..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[2][4](紫格)。这段棍子从 3 到 5,长度 2。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 2;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 2,候选总成本 2。
候选 2 刷新了最优,暂定 dp[2][4]=2,对应「第一刀先切 arr[3]=4」。
区间内所有候选 k 试完,dp[2][4]=2 锁定(变绿)。它代表把 3..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[3][5](紫格)。这段棍子从 4 到 7,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[3][4]=0 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
候选 3 刷新了最优,暂定 dp[3][5]=3,对应「第一刀先切 arr[4]=5」。
区间内所有候选 k 试完,dp[3][5]=3 锁定(变绿)。它代表把 4..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[0][3](紫格)。这段棍子从 0 到 4,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][3]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
候选 7 刷新了最优,暂定 dp[0][3]=7,对应「第一刀先切 arr[1]=1」。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
候选 7 没有更小,但同样达到 7,属于并列最优;表里保留先记录的那个,结果不变。
区间内所有候选 k 试完,dp[0][3]=7 锁定(变绿)。它代表把 0..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[1][4](紫格)。这段棍子从 1 到 5,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
候选 6 刷新了最优,暂定 dp[1][4]=6,对应「第一刀先切 arr[2]=3」。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
候选 7 没比当前最优 6 更省,这种劈法不划算,保留原最优。
区间内所有候选 k 试完,dp[1][4]=6 锁定(变绿)。它代表把 1..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[2][5](紫格)。这段棍子从 3 到 7,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
候选 7 刷新了最优,暂定 dp[2][5]=7,对应「第一刀先切 arr[3]=4」。
试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[2][4]=2 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
候选 6 刷新了最优,暂定 dp[2][5]=6,对应「第一刀先切 arr[4]=5」。
区间内所有候选 k 试完,dp[2][5]=6 锁定(变绿)。它代表把 3..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[0][4](紫格)。这段棍子从 0 到 5,长度 5。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 5;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][4]=6(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 11。
候选 11 刷新了最优,暂定 dp[0][4]=11,对应「第一刀先切 arr[1]=1」。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 10。
候选 10 刷新了最优,暂定 dp[0][4]=10,对应「第一刀先切 arr[2]=3」。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 12。
候选 12 没比当前最优 10 更省,这种劈法不划算,保留原最优。
区间内所有候选 k 试完,dp[0][4]=10 锁定(变绿)。它代表把 0..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[1][5](紫格)。这段棍子从 1 到 7,长度 6。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 6;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
候选 12 刷新了最优,暂定 dp[1][5]=12,对应「第一刀先切 arr[2]=3」。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[1][4]=6 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
区间内所有候选 k 试完,dp[1][5]=12 锁定(变绿)。它代表把 1..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
轮到 dp[0][5](紫格)。这段棍子从 0 到 7,长度 7。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 7;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][5]=12(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 19。
候选 19 刷新了最优,暂定 dp[0][5]=19,对应「第一刀先切 arr[1]=1」。
试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 16。
候选 16 刷新了最优,暂定 dp[0][5]=16,对应「第一刀先切 arr[2]=3」。
试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[0][4]=10 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
区间内所有候选 k 试完,dp[0][5]=16 锁定(变绿)。它代表把 0..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
填到最右上角 dp[0][5]=16,它代表把整根棍子 0..7 的所有切点切开的最小总成本,就是最终答案 16。
只有一个切点时,成本恒等于整根长度;切点越多,切割顺序越关键,才需要 DP。
两个高频追问:为何枚举第一刀就够,以及 DP 如何把「顺序」隐藏进区间递归。
参考代码
from typing import Listclass Solution: def minCost(self, n: int, cuts: List[int]) -> int: arr = [0] + sorted(cuts) + [n] m = len(arr) dp = [[0] * m for _ in range(m)] for length in range(2, m): for i in range(m - length): j = i + length dp[i][j] = min(dp[i][k] + dp[k][j] + arr[j] - arr[i] for k in range(i + 1, j)) return dp[0][m - 1]复杂度
- 时间：O(c³)，区间端点数 c≈cuts 长度,枚举区间 O(c²)、每个区间再枚举一刀 O(c)
- 空间：O(c²)，二维 dp 表,大小 (c+2)×(c+2)
易错点
面试追问把动画讲成自己的话
追问为什么枚举区间里的「第一刀」就能覆盖所有切法?
追问为什么切割顺序会影响总成本,DP 却能不显式枚举顺序?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题