钢条切割

概述

钢条切割问题是动态规划的入门经典问题：给定一根长度为 $n$ 的钢条和价格表 $p$，求切割方案使总收益最大。该问题同时展示了最优子结构和重叠子问题两个核心性质，是理解动态规划思想的最佳起点。

定义

钢条切割问题（Rod Cutting）

输入：长度为 $n$ 的钢条，价格表 $p[\mathrm{1..}n]$，其中 $p[i]$ 表示长度为 $i$ 的钢条的售价。

输出：一个切割方案，使得所有切割段的售价之和最大。

设 $r[i]$ 为长度为 $i$ 的钢条的最大收益，则： $r[i]={\max }_{1\le j\le i}\{p[j]+r[i-j]\}$

其中 $r[0]=0$（长度为0的钢条收益为0）。

核心性质

1. 最优子结构

长度为 $n$ 的钢条的最优切割方案中，第一刀切下长度 $j$ 后，剩余长度 $n-j$ 的钢条也必须按最优方式切割。否则，将剩余部分替换为更优的切割方案，可得到更大的总收益——矛盾。

这意味着我们可以将问题分解为：选择第一刀的位置 $j$，然后对剩余部分递归求解。

2. 重叠子问题

朴素递归求解时，子问题被大量重复计算。例如，计算 $r[4]$ 时：

• 路径 $r[4]\to r[3]\to r[2]\to r[1]$
• 路径 $r[4]\to r[3]\to r[1]$（通过 $j=2$）
• 路径 $r[4]\to r[2]\to r[1]$
• 路径 $r[4]\to r[1]$（通过 $j=3$）

$r[1]$ 被计算了4次，$r[2]$ 被计算了2次。朴素递归的时间复杂度为 $O(2^n)$。

3. 自顶向下（备忘录）实现

MEMOIZED-CUT-ROD(p, n):
    let r[0..n] be a new array, initialized to -∞
    return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r):
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else:
        q = -∞
        for i = 1 to n:
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
    r[n] = q
    return q

4. 自底向上实现

BOTTOM-UP-CUT-ROD(p, n):
    r[0] = 0
    for j = 1 to n:
        q = -∞
        for i = 1 to j:
            q = max(q, p[i] + r[j-i])
        r[j] = q
    return r[n]

5. 构造最优解

为了不仅得到最大收益，还要得到具体的切割方案，需要维护一个辅助数组 $s[\mathrm{1..}n]$，记录第一刀的最优切割位置：

EXTENDED-BOTTOM-UP-CUT-ROD(p, n):
    r[0] = 0
    for j = 1 to n:
        q = -∞
        for i = 1 to j:
            if q < p[i] + r[j-i]:
                q = p[i] + r[j-i]
                s[j] = i    // 记录第一刀切下长度 i
        r[j] = q
    return r and s

PRINT-CUT-ROD-SOLUTION(p, n):
    while n > 0:
        print s[n]
        n = n - s[n]

复杂度分析

方法	时间复杂度	空间复杂度
朴素递归	$O(2^n)$	$O(n)$（递归栈）
备忘录（自顶向下）	$O(n^2)$	$O(n)$
自底向上	$O(n^2)$	$O(n)$

章节扩展

• 14.1 钢条切割 — 钢条切割问题的完整求解过程
• 动态规划 — 动态规划完整方法论
• 最优子结构 — 最优子结构性质的详细说明
• 重叠子问题 — 重叠子问题性质的详细说明

参见

• 矩阵链乘法 — 另一个经典动态规划问题
• 最长公共子序列 — 字符串上的动态规划
• 最优二叉搜索树 — 树结构上的动态规划