1. 概述
钢条切割问题是一个经典的优化问题，核心目标是找到切割钢条的最佳方式，以实现总收益最大化。
本教程将深入理解钢条切割问题，并探索多种Java解决方案。
2. 问题解析
假设有一根长度为 n 的钢条。我们可以将其切割成不同长度的小段出售，并拥有一个价格表记录不同长度钢条的价格。我们的目标是通过最优切割方案获得最大收益。
以长度 n=4 的钢条为例，价格数组 Pi = [1,5,8,9]。Pi 数组表示长度为 i 的钢条价格：
- P1 = 1：长度1的钢条价格1单位
- P2 = 5：长度2的钢条价格5单位
- P3 = 8：长度3的钢条价格8单位
- P4 = 9：长度4的钢条价格9单位
对于长度4的钢条，可能的切割方案及收益如下：
- 切成4段1米 [1,1,1,1]，收益 = 1+1+1+1 = $4
- 切成2段2米 [2,2]，收益 = 5+5 = $10
- 不切割 [4]，收益 = $9
- 切成1米和2米组合 [1,1,2]，收益 = 1+1+5 = $7
- 切成1米和2米组合 [1,2,1]，收益 = 1+5+1 = $7
- 切成1米和2米组合 [2,1,1]，收益 = 5+1+1 = $7
显然，切成两段2米的方案收益最高（$10），其他组合均低于此值，这就是最优解。
3. 递归解法
递归解法通过分解子问题并递归求解。其递推关系为 *Rn = max₁≤ᵢ≤ₙ(Pᵢ + Rₙ₋ᵢ)*，其中：
- Rn：长度 n 钢条的最大收益
- Pi：长度 i 钢条的价格
int usingRecursion(int[] prices, int n) {
if (n <= 0) {
return 0;
}
int maxRevenue = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
maxRevenue = Math.max(maxRevenue, prices[i - 1] + usingRecursion(prices, n - i));
}
return maxRevenue;
}
代码逻辑：
- 基线条件：钢条长度≤0时收益为0
- 遍历所有可能的切割长度
- 递归计算每种切割方案的收益并取最大值
测试用例：
@Test
void givenARod_whenUsingRecursion_thenFindMaxRevenue() {
int[] prices = {1, 5, 8, 9};
int rodLength = 4;
int maxRevenue = RodCuttingProblem.usingRecursion(prices, rodLength);
assertEquals(10, maxRevenue);
}
⚠️ 性能瓶颈：虽然递归解法直观易懂，但其指数级时间复杂度 O(2ⁿ) 使其难以处理大规模问题。例如4米钢条需要 2⁴=16 次迭代，而10米钢条将需要 1024 次迭代！
❌ 主要缺陷：
- 重复计算相同子问题
- 可能导致栈溢出
- 无显式状态存储（依赖调用栈）
4. 记忆化递归解法
通过记忆化技术优化递归解法，使用备忘录表存储子问题解：
int usingMemoizedRecursion(int[] prices, int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return memoizedHelper(prices, n, memo);
}
int memoizedHelper(int[] prices, int n, int[] memo) {
if (n <= 0) {
return 0;
}
if (memo[n] != -1) {
return memo[n];
}
int maxRevenue = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
maxRevenue = Math.max(maxRevenue, prices[i - 1] + memoizedHelper(prices, n - i, memo));
}
memo[n] = maxRevenue;
return maxRevenue;
}
关键改进：
- 备忘录数组
memo存储已计算结果 - 避免重复计算子问题
测试用例：
@Test
void givenARod_whenUsingMemoizedRecursion_thenFindMaxRevenue() {
int[] prices = {1, 5, 8, 9};
int rodLength = 4;
int maxRevenue = RodCuttingProblem.usingMemoizedRecursion(prices, rodLength);
assertEquals(10, maxRevenue);
}
✅ 性能提升：
- 时间复杂度降至 O(n²)（相比之前的指数级）
- 空间复杂度 O(n) 用于存储备忘录
⚠️ 空间代价：需要额外空间存储子问题解，但相比时间优化是值得的。
5. 动态规划解法
动态规划通过分解子问题并只求解一次来优化，与分治法类似但避免重复计算。
5.1. 迭代（自底向上）法
int usingDynamicProgramming(int[] prices, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int maxRevenue = Integer.MIN_VALUE;
for (int j = 1; j <= i; j++) {
maxRevenue = Math.max(maxRevenue, prices[j - 1] + dp[i - j]);
}
dp[i] = maxRevenue;
}
return dp[n];
}
核心思想：
dp数组存储各长度最优解- 从小到大逐步构建解
测试用例：
@Test
void givenARod_whenUsingDynamicProgramming_thenFindMaxRevenue() {
int[] prices = {1, 5, 8, 9};
int rodLength = 4;
int maxRevenue = RodCuttingProblem.usingDynamicProgramming(prices, rodLength);
assertEquals(10, maxRevenue);
}
✅ 优势：
- 消除递归调用开销
- 无需额外备忘录表
- 时间复杂度 O(n²)，空间复杂度 O(n)
5.2. 无界背包解法
无界背包问题允许重复选择物品，对应钢条切割中可重复使用同一切割长度：
int usingUnboundedKnapsack(int[] prices, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < prices.length; j++) {
if (j + 1 <= i) {
dp[i] = Math.max(dp[i], dp[i - (j + 1)] + prices[j]);
}
}
}
return dp[n];
}
实现特点：
- 外层循环遍历钢条长度
- 内层循环遍历价格表
- 通过
dp[i - (j+1)]实现重复选择
测试用例：
@Test
void givenARod_whenUsingGreedy_thenFindMaxRevenue() {
int[] prices = {1, 5, 8, 9};
int rodLength = 4;
int maxRevenue = RodCuttingProblem.usingUnboundedKnapsack(prices, rodLength);
assertEquals(10, maxRevenue);
}
⚠️ 潜在问题：空间复杂度可能增加，但时间复杂度仍为 O(n²)。
6. 总结
本文探讨了钢条切割问题的多种Java解法：
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归 | O(2ⁿ) | O(n) | 小规模问题，教学演示 |
| 记忆化递归 | O(n²) | O(n) | 中等规模，需要快速实现 |
| 动态规划（迭代） | O(n²) | O(n) | 大规模问题，生产环境 |
| 无界背包 | O(n²) | O(n) | 需要重复选择切割方案 |
核心权衡点：
- ✅ 递归：实现简单但性能差
- ✅ 记忆化：平衡时间与空间
- ✅ 动态规划：最优性能但实现稍复杂
实际选择需根据具体场景权衡时间、空间和实现复杂度。对于生产环境，推荐使用动态规划解法。
本文所有示例代码可在 GitHub 获取。