Rod Cutting Problem
你有一根长度为 n 的杆，其中 n = prices.length。长度为 k 的杆段售价为 prices[k-1]。你可以把杆切成任意数量的整数长度杆段，也可以整根出售。返回出售整根杆所能赚到的最多金额。
函数
- pricesinteger-array
- prices[k-1] 是长度为 k 的一段木棒的价格；木棒长度为 prices.length。
- 返回值integer
- 整根杆子最多能赚到的钱
约束条件
1 ≤ prices.length ≤ 10001 ≤ prices[i] ≤ 105
示例
- 输入
- prices = [2, 5, 7, 8]
- 输出
- 10
- 解释
- 两段长度为 2 的木棍可以卖 5 + 5 = 10。整根卖掉能赚 8，切成一段长度为 1 的和一段长度为 3 的木棍能赚 2 + 7 = 9。
- 输入
- prices = [1, 3, 8]
- 输出
- 8
- 解释
- 整根长度为 3 的杆子售价为 8。最佳切法是切成长度为 1 和 2 的两段，但总共只能赚到 1 + 3 = 4，所以你不切割。
- 输入
- prices = [4, 6, 9, 11, 14]
- 输出
- 20
- 解释
- 长度为 1 的段每段售价为 4，比任何更长的段单位长度售价都高，而且能切成 5 段，所以把木棒切成 5 段长度为 1 的小段可以赚 20。
进阶
如果最多可以切割木棒 m 次，那么每个表格项需要知道什么？
提示
逐个打开提示，每个都会多透露一点。
每种切割钢条的方式都从左端开始有一段长度为 1 到
n的首段。卖出这段后，还需要决定什么？切下第一段长度为
k的木条后，剩下的木条长度为n-k，而出售剩余木条的最佳方式与已经切下的那段无关。因此，你需要知道每种较短长度对应的最高售价，总共只有n+1种长度。按从短到长的顺序填充
best[0..n]。best[0]是 0，而best[len]是所有从 1 到len的k对应的prices[k-1] + best[len-k]中的最大值。选择k = len表示整段出售。
题解
一根长度为 n 的杆有 2^(n-1) 种切割方式。你不需要考虑所有方式：无论第一段有多长，剩下的部分都是更短的杆，面临同样的问题。因此，答案只有 n+1 个，每种长度对应一个。从最短的开始逐一求出这些答案，需要 O(n²) 步。
尝试第一块的所有长度
结果正确，但无法在最大的测试中运行完毕
思路
无论采用什么方案，左端的那段长度都是 k，范围从 1 到木棍的长度，并能卖出 prices[k-1]；方案剩下的部分会把一根长度为 length-k 的木棍切开。因此，长度为 0 时，best(length) 的值是 0；否则，它的值就是所有 prices[k-1] + best(length-k) 中的最大值，其中 k = length 表示整根木棍直接出售。每种方案都有第一段木棍，因此这个最大值涵盖了所有方案。
每次调用都会分支到每个更短的长度，因此调用次数会随着长度的每个单位翻倍：一根长度为 40 的木棍会产生约 2^40 次调用，也就是 10^12 次调用。
算法
- 编写
best(length)，当 length 为 0 时返回 0。 - 对于从 1 到
length的每个第一段长度k，计算prices[k-1] + best(length-k)。 - 返回这些值中最大的值。
- 返回
best(n)。
def cutRod(prices):
# The most money a rod of this length can earn
def best(length):
top = 0
for piece in range(1, length + 1):
# sell a first piece of this length, then cut the rest as well as possible
top = max(top, prices[piece - 1] + best(length - piece))
return top
return best(len(prices))每种长度的最优价格，按最短长度优先
思路
递归会重复计算相同的值：best(2)会被best(3)、best(4)以及每个更长的木棍调用。长度只有 n+1 种，所以把每种长度的结果计算一次并存入数组best。每种长度只会读取更短长度的结果，因此从 0 开始向上填充数组，就能确保读取时所需的值都已就绪。
对于[2, 5, 7, 8]：best[1]是 2，best[2]是 2 + 2 和 5 中较大的值，也就是 5，best[3]是 7，best[4]是 2 + 7、5 + 5、7 + 2 和 8 中最大的值，也就是 10。
与 0/1 背包不同，best[len-k]中可能已经包含长度为k的木块，而这正是你想要的结果，因为每种长度的木棍都可以切任意多次。长度为len时要尝试len种第一段长度，总共需要 n(n+1)/2 步；对于长度为 1000 的木棍，大约需要 5 × 10^5 步。
算法
- 创建
best，使其包含n + 1个元素，且全部为 0。 - 对于从 1 到 n 的每个
length，尝试从 1 到length的每个首段长度k。 - 计算
prices[k-1] + best[length-k]，并将最大值保存在best[length]中。 - 返回
best[n]。
def cutRod(prices):
n = len(prices)
# best[length]: the most money a rod of that length can earn
best = [0] * (n + 1)
for length in range(1, n + 1):
for piece in range(1, length + 1):
# a first piece of this length, then the best for what is left
earned = prices[piece - 1] + best[length - piece]
if earned > best[length]:
best[length] = earned
return best[n]
易错点和边界情况
- 读取
prices[k]，其中长度为k。这样每件都会按长一单位的尺寸定价，并且在k = n时越界；应使用prices[k-1]。 - 漏掉
k = length，也就是不切割的整段。这样best[1]会保持为 0，而[1, 3, 8]的得分会是 3，而不是 8。 - 按照单位长度的最高价格贪心切割。对于
[2, 7, 11, 13]，长度为 3 的段单位价格最高，但它的价格是 11，加上剩余部分的 2，得分是 13；而切成两段长度为 2 的段，得分是 14。 - 在 Python 中使用自顶向下的记忆化。递归嵌套的深度仍会和杆的长度一样：长度为 1000 的杆会嵌套 1001 次调用，超过默认的 1000 次限制。请自底向上填充数组。
常见问题4
钢条切割问题的时间复杂度是多少？
这个表格需要 O(n²) 时间和 O(n) 内存：长度为 len 时，会尝试 len 个首段，总共会尝试 n(n+1)/2 次。如果不存储答案，对于长度为 n 的杆，递归会恰好调用 2^n 次，因为每种长度都会调用所有更短的长度。
为什么钢条切割是无界背包问题？
把每段长度为 k 的部分看作重量为 k、价值为 prices[k-1] 的物品，且物品数量不限；把杆子看作容量为 n 的背包，并且必须恰好装满。这样，物品的最大总价值就是杆子的最高价格。
如何找到切割木棒的位置？
对于每种长度，保存使价格最高的第一个切割长度 k。从长度 n 开始：切下一段已保存长度的木料，转到剩余的长度，然后重复这个过程，直到长度变为 0。这些木料就组成了一个最优方案。
如果每次切割都要花钱，答案会有什么变化？
整根卖出不需要切割，而其他所有第一段长度都会增加一次切割。因此，best[len] 取 prices[len-1] 和所有小于 len 的 k 对应的 prices[k-1] + best[len-k] - cost 中的最大值。表格的其余部分保持不变。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def cutRod(prices):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
prices = [2, 5, 7, 8]
预期输出
10