LeetCode 1547困难区间DP

切棍子的最小成本图解题解

这道题到底在问什么

长度为 n 的木棍要在 cuts 指定的位置全部切开。每次切割的成本等于当前被切那段木棍的长度。可以任意安排切割顺序,返回完成所有切割的最小总成本。

输入: n=7, cuts=[1,3,4,5]
输出: 16（枚举第一刀切哪个点,取拆出的两子段总成本最小的那种）
输入: n=2, cuts=[1]
输出: 2（只有一刀,成本就是整根长度 2）

先想最直接的笨办法

一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。（动画第 3 步）

最优解：一步一步想明白

3一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。
4先看表骨架:行列都对应排序后的端点 arr=[0, 1, 3, 4, 5, 7]。dp[i][j] 是「切开 arr[i] 到 arr[j] 之间所有切点」的最小成本。对角线、下方,以及相邻端点(j 比 i 大 1)这些格子里都没有内部切点,成本 0,已经直接填好;只有上三角里跨度更大的「·」还没算,我们从最短的区间开始填。
5轮到 dp[0][2](紫格)。这段棍子从 0 到 3,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
6试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][2]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
7候选 3 刷新了最优,暂定 dp[0][2]=3,对应「第一刀先切 arr[1]=1」。
8区间内所有候选 k 试完,dp[0][2]=3 锁定(变绿)。它代表把 0..3 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
9轮到 dp[1][3](紫格)。这段棍子从 1 到 4,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
10试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
11候选 3 刷新了最优,暂定 dp[1][3]=3,对应「第一刀先切 arr[2]=3」。
12区间内所有候选 k 试完,dp[1][3]=3 锁定(变绿)。它代表把 1..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
13轮到 dp[2][4](紫格)。这段棍子从 3 到 5,长度 2。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 2;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
14试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 2,候选总成本 2。
15候选 2 刷新了最优,暂定 dp[2][4]=2,对应「第一刀先切 arr[3]=4」。
16区间内所有候选 k 试完,dp[2][4]=2 锁定(变绿)。它代表把 3..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
17轮到 dp[3][5](紫格)。这段棍子从 4 到 7,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
18试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[3][4]=0 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
19候选 3 刷新了最优,暂定 dp[3][5]=3,对应「第一刀先切 arr[4]=5」。
20区间内所有候选 k 试完,dp[3][5]=3 锁定(变绿)。它代表把 4..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
21轮到 dp[0][3](紫格)。这段棍子从 0 到 4,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
22试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][3]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
23候选 7 刷新了最优,暂定 dp[0][3]=7,对应「第一刀先切 arr[1]=1」。
24试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
25候选 7 没有更小,但同样达到 7,属于并列最优;表里保留先记录的那个,结果不变。
26区间内所有候选 k 试完,dp[0][3]=7 锁定(变绿)。它代表把 0..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
27轮到 dp[1][4](紫格)。这段棍子从 1 到 5,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
28试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
29候选 6 刷新了最优,暂定 dp[1][4]=6,对应「第一刀先切 arr[2]=3」。
30试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
31候选 7 没比当前最优 6 更省,这种劈法不划算,保留原最优。
32区间内所有候选 k 试完,dp[1][4]=6 锁定(变绿)。它代表把 1..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
33轮到 dp[2][5](紫格)。这段棍子从 3 到 7,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
34试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
35候选 7 刷新了最优,暂定 dp[2][5]=7,对应「第一刀先切 arr[3]=4」。
36试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[2][4]=2 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
37候选 6 刷新了最优,暂定 dp[2][5]=6,对应「第一刀先切 arr[4]=5」。
38区间内所有候选 k 试完,dp[2][5]=6 锁定(变绿)。它代表把 3..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
39轮到 dp[0][4](紫格)。这段棍子从 0 到 5,长度 5。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 5;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
40试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][4]=6(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 11。
41候选 11 刷新了最优,暂定 dp[0][4]=11,对应「第一刀先切 arr[1]=1」。
42试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 10。
43候选 10 刷新了最优,暂定 dp[0][4]=10,对应「第一刀先切 arr[2]=3」。
44试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 12。
45候选 12 没比当前最优 10 更省,这种劈法不划算,保留原最优。
46区间内所有候选 k 试完,dp[0][4]=10 锁定(变绿)。它代表把 0..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
47轮到 dp[1][5](紫格)。这段棍子从 1 到 7,长度 6。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 6;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
48试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
49候选 12 刷新了最优,暂定 dp[1][5]=12,对应「第一刀先切 arr[2]=3」。
50试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
51候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
52试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[1][4]=6 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
53候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
54区间内所有候选 k 试完,dp[1][5]=12 锁定(变绿)。它代表把 1..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
55轮到 dp[0][5](紫格)。这段棍子从 0 到 7,长度 7。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 7;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
56试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][5]=12(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 19。
57候选 19 刷新了最优,暂定 dp[0][5]=19,对应「第一刀先切 arr[1]=1」。
58试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 16。
59候选 16 刷新了最优,暂定 dp[0][5]=16,对应「第一刀先切 arr[2]=3」。
60试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
61候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
62试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[0][4]=10 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
63候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
64区间内所有候选 k 试完,dp[0][5]=16 锁定(变绿)。它代表把 0..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
65填到最右上角 dp[0][5]=16,它代表把整根棍子 0..7 的所有切点切开的最小总成本,就是最终答案 16。

⚠️ 容易写错的地方

✗ 错：忘了补两端、或切点没排序就直接 DP

✓ 对：arr = [0] + sorted(cuts) + [n] 补端点再排序

区间成本靠「端点之差」算,缺两端算不出真实段长;不排序会让 arr[j]-arr[i] 变负或错位

✗ 错：把这一刀的代价当成跟 k 有关

✓ 对：代价固定为 arr[j]-arr[i],与 k 无关

切「第一刀」时整段还连着,面对的就是整段,长度只取决于区间两端

✗ 错：C++/Java 忘了把 dp[i][j] 先设成大数

✓ 对：初始化 INT_MAX/2 再取 min

默认 0 会让 min 永远取到 0,得到错误的最小成本

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

Python

from typing import List
class 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]

C++

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0); cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();
        vector<vector<int>> dp(m, vector<int>(m));
        for (int len = 2; len < m; ++len) for (int i = 0; i + len < m; ++i) {
            int j = i + len;
            dp[i][j] = INT_MAX / 2;
            for (int k = i + 1; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
        }
        return dp[0][m-1];
    }
};

Java

import java.util.*;
class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length + 2;
        int[] arr = new int[m];
        arr[0] = 0; arr[m - 1] = n;
        System.arraycopy(cuts, 0, arr, 1, cuts.length);
        Arrays.sort(arr);
        int[][] dp = new int[m][m];
        for (int len = 2; len < m; len++) for (int i = 0; i + len < m; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE / 2;
            for (int k = i + 1; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + arr[j] - arr[i]);
        }
        return dp[0][m - 1];
    }
}

复杂度

时间

O(c³)

区间端点数 c≈cuts 长度,枚举区间 O(c²)、每个区间再枚举一刀 O(c)

空间

O(c²)

二维 dp 表,大小 (c+2)×(c+2)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着切棍子的最小成本的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么枚举区间里的「第一刀」就能覆盖所有切法?+

因为不管整体切割顺序多复杂,某个区间里总有「第一个被切」的那刀,而它落下时整段还连着,代价必然是整段长度 arr[j]-arr[i]。枚举这第一刀的位置 k,就把所有可能的切法按「区间里谁先切」分了类;切完后区间被劈成 [i,k] 与 [k,j] 两段,互不影响、各自独立求最优(即更短区间的 dp)。按区间长度从短到长填表,依赖的子区间一定都已算好。这是区间 DP 的通用套路。

为什么切割顺序会影响总成本,DP 却能不显式枚举顺序?+

因为每一刀的代价只跟它所在那段当时的长度有关。DP 把「整体顺序」拆成「每个区间里第一刀先切哪一刀」的递归决策:定下第一刀后,左右两段各自的最优切法已被子问题封装,无需关心它们内部的具体顺序,从而把指数级的顺序枚举压成多项式。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把切棍子的最小成本一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1547困难区间DP

切棍子的最小成本图解题解

这道题到底在问什么

输入: n=7, cuts=[1,3,4,5]
输出: 16（枚举第一刀切哪个点,取拆出的两子段总成本最小的那种）
输入: n=2, cuts=[1]
输出: 2（只有一刀,成本就是整根长度 2）

先想最直接的笨办法

一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。（动画第 3 步）

最优解：一步一步想明白

3一句话套路:在每个区间里枚举「第一刀先切哪一刀」,这一刀把整段劈成左右两个更小的子区间。下面按区间从短到长逐格填这张 dp 表。
4先看表骨架:行列都对应排序后的端点 arr=[0, 1, 3, 4, 5, 7]。dp[i][j] 是「切开 arr[i] 到 arr[j] 之间所有切点」的最小成本。对角线、下方,以及相邻端点(j 比 i 大 1)这些格子里都没有内部切点,成本 0,已经直接填好;只有上三角里跨度更大的「·」还没算,我们从最短的区间开始填。
5轮到 dp[0][2](紫格)。这段棍子从 0 到 3,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
6试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][2]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
7候选 3 刷新了最优,暂定 dp[0][2]=3,对应「第一刀先切 arr[1]=1」。
8区间内所有候选 k 试完,dp[0][2]=3 锁定(变绿)。它代表把 0..3 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
9轮到 dp[1][3](紫格)。这段棍子从 1 到 4,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
10试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
11候选 3 刷新了最优,暂定 dp[1][3]=3,对应「第一刀先切 arr[2]=3」。
12区间内所有候选 k 试完,dp[1][3]=3 锁定(变绿)。它代表把 1..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
13轮到 dp[2][4](紫格)。这段棍子从 3 到 5,长度 2。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 2;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
14试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 2,候选总成本 2。
15候选 2 刷新了最优,暂定 dp[2][4]=2,对应「第一刀先切 arr[3]=4」。
16区间内所有候选 k 试完,dp[2][4]=2 锁定(变绿)。它代表把 3..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
17轮到 dp[3][5](紫格)。这段棍子从 4 到 7,长度 3。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 3;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
18试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[3][4]=0 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 3,候选总成本 3。
19候选 3 刷新了最优,暂定 dp[3][5]=3,对应「第一刀先切 arr[4]=5」。
20区间内所有候选 k 试完,dp[3][5]=3 锁定(变绿)。它代表把 4..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
21轮到 dp[0][3](紫格)。这段棍子从 0 到 4,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
22试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][3]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
23候选 7 刷新了最优,暂定 dp[0][3]=7,对应「第一刀先切 arr[1]=1」。
24试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][3]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
25候选 7 没有更小,但同样达到 7,属于并列最优;表里保留先记录的那个,结果不变。
26区间内所有候选 k 试完,dp[0][3]=7 锁定(变绿)。它代表把 0..4 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
27轮到 dp[1][4](紫格)。这段棍子从 1 到 5,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
28试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
29候选 6 刷新了最优,暂定 dp[1][4]=6,对应「第一刀先切 arr[2]=3」。
30试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
31候选 7 没比当前最优 6 更省,这种劈法不划算,保留原最优。
32区间内所有候选 k 试完,dp[1][4]=6 锁定(变绿)。它代表把 1..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
33轮到 dp[2][5](紫格)。这段棍子从 3 到 7,长度 4。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 4;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
34试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[2][3]=0 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 7。
35候选 7 刷新了最优,暂定 dp[2][5]=7,对应「第一刀先切 arr[3]=4」。
36试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[2][4]=2 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 4,候选总成本 6。
37候选 6 刷新了最优,暂定 dp[2][5]=6,对应「第一刀先切 arr[4]=5」。
38区间内所有候选 k 试完,dp[2][5]=6 锁定(变绿)。它代表把 3..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
39轮到 dp[0][4](紫格)。这段棍子从 0 到 5,长度 5。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 5;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
40试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][4]=6(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 11。
41候选 11 刷新了最优,暂定 dp[0][4]=11,对应「第一刀先切 arr[1]=1」。
42试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][4]=2(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 10。
43候选 10 刷新了最优,暂定 dp[0][4]=10,对应「第一刀先切 arr[2]=3」。
44试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][4]=0(两个蓝色依赖格),再加上这一刀的段长 5,候选总成本 12。
45候选 12 没比当前最优 10 更省,这种劈法不划算,保留原最优。
46区间内所有候选 k 试完,dp[0][4]=10 锁定(变绿)。它代表把 0..5 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
47轮到 dp[1][5](紫格)。这段棍子从 1 到 7,长度 6。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 6;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
48试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[1][2]=0 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
49候选 12 刷新了最优,暂定 dp[1][5]=12,对应「第一刀先切 arr[2]=3」。
50试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[1][3]=3 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
51候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
52试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[1][4]=6 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 6,候选总成本 12。
53候选 12 没有更小,但同样达到 12,属于并列最优;表里保留先记录的那个,结果不变。
54区间内所有候选 k 试完,dp[1][5]=12 锁定(变绿)。它代表把 1..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
55轮到 dp[0][5](紫格)。这段棍子从 0 到 7,长度 7。不管第一刀切在哪,此刻整段还连着,切它都得付一次段长 7;我们试遍每个候选 k,看哪种劈法两侧子区间加起来最省。
56试「第一刀先切 arr[1]=1」:它把整段劈成左段 dp[0][1]=0 和右段 dp[1][5]=12(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 19。
57候选 19 刷新了最优,暂定 dp[0][5]=19,对应「第一刀先切 arr[1]=1」。
58试「第一刀先切 arr[2]=3」:它把整段劈成左段 dp[0][2]=3 和右段 dp[2][5]=6(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 16。
59候选 16 刷新了最优,暂定 dp[0][5]=16,对应「第一刀先切 arr[2]=3」。
60试「第一刀先切 arr[3]=4」:它把整段劈成左段 dp[0][3]=7 和右段 dp[3][5]=3(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
61候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
62试「第一刀先切 arr[4]=5」:它把整段劈成左段 dp[0][4]=10 和右段 dp[4][5]=0(两个蓝色依赖格),再加上这一刀的段长 7,候选总成本 17。
63候选 17 没比当前最优 16 更省,这种劈法不划算,保留原最优。
64区间内所有候选 k 试完,dp[0][5]=16 锁定(变绿)。它代表把 0..7 之间的切点全切开的最小成本,更长的区间会直接拿它当子结果。
65填到最右上角 dp[0][5]=16,它代表把整根棍子 0..7 的所有切点切开的最小总成本,就是最终答案 16。

⚠️ 容易写错的地方

✗ 错：忘了补两端、或切点没排序就直接 DP

✓ 对：arr = [0] + sorted(cuts) + [n] 补端点再排序

区间成本靠「端点之差」算,缺两端算不出真实段长;不排序会让 arr[j]-arr[i] 变负或错位

✗ 错：把这一刀的代价当成跟 k 有关

✓ 对：代价固定为 arr[j]-arr[i],与 k 无关

切「第一刀」时整段还连着,面对的就是整段,长度只取决于区间两端

✗ 错：C++/Java 忘了把 dp[i][j] 先设成大数

✓ 对：初始化 INT_MAX/2 再取 min

默认 0 会让 min 永远取到 0,得到错误的最小成本

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

Python

from typing import List
class 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]

C++

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        cuts.push_back(0); cuts.push_back(n);
        sort(cuts.begin(), cuts.end());
        int m = cuts.size();
        vector<vector<int>> dp(m, vector<int>(m));
        for (int len = 2; len < m; ++len) for (int i = 0; i + len < m; ++i) {
            int j = i + len;
            dp[i][j] = INT_MAX / 2;
            for (int k = i + 1; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cuts[j] - cuts[i]);
        }
        return dp[0][m-1];
    }
};

Java

import java.util.*;
class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length + 2;
        int[] arr = new int[m];
        arr[0] = 0; arr[m - 1] = n;
        System.arraycopy(cuts, 0, arr, 1, cuts.length);
        Arrays.sort(arr);
        int[][] dp = new int[m][m];
        for (int len = 2; len < m; len++) for (int i = 0; i + len < m; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE / 2;
            for (int k = i + 1; k < j; k++) dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + arr[j] - arr[i]);
        }
        return dp[0][m - 1];
    }
}

复杂度

时间

O(c³)

区间端点数 c≈cuts 长度,枚举区间 O(c²)、每个区间再枚举一刀 O(c)

空间

O(c²)

二维 dp 表,大小 (c+2)×(c+2)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着切棍子的最小成本的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么枚举区间里的「第一刀」就能覆盖所有切法?+

为什么切割顺序会影响总成本,DP 却能不显式枚举顺序?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

切棍子的最小成本 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

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

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

切棍子的最小成本 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

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

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

切棍子的最小成本图解题解

切棍子的最小成本图解题解