给定杆长和前3根杆的P（价格）。我们将填写其余棒料的可能价格。假设我们可以根据需要切割更长的碎片。
L = 1 2 3 4 5 6 7 8
p = 3 8 12
我们基本上想得到每一个丢失的价格都能得到的最高价格。
我的方法
我相信，既然我们得到了长度为1、2和3的杆的最佳价格，我们就可以为下一根杆生成所有可能的组合。
For example to get price of rod where L = 4
price of rod where L = 1 + rod where L = 3 = 15
price of rod where L = 2 + rode where L = 2 = 16
Therefore price of rod wehre L = 4 = 16 since 16 > 15.
For example to get price of rod where L = 5
price of rod where L = 1 + rod where L = 2 and rod where L = 2 = 19
price of rod where L = 3 + rod where L = 2 = 20
price of rod where L = 4 + rod where L = 1 = 19
所以这就是我所遵循的方法但是我不确定我是否正确。我也希望有人能验证这种方法，也可能帮助我从中得出一个公式我不是在寻找代码，因为理解这个问题就足以编写代码。
最佳答案
您可以在CLRS（第360页，第15.1节）中查看对此问题的解释。这个问题叫做切杆问题。
您的方法是正确的，您可以将其形式化为递归关系。
f(n) = min(f(n - i) + price(i)). 1 <= i <= n - 1
其中
f(n)是购买长度为n的杆的最低价格。使用memoization，这可以在
O(n^2)中计算。