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

一根木棍随便切，为什么顺序不同总价会差这么多

给一根长度 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²)。

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