algorithm - 查找棒材切割的价格

Question

给定杆的长度和前 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

这就是我所遵循的方法。但是我不确定我是否正确。如果有人可以验证这种方法并且也可以帮助我从中推导出一个公式，我也希望如此。我不是在寻找代码，因为了解问题足以编写代码。

Answer 1

您可以在 CLRS 中查看此问题变体的解释。 (第 15.1 节，第 360 页)。该问题称为杆切割问题。

您的做法是正确的，您可以将其形式化为递归关系。

f(n) = min(f(n - i) + price(i)).    1 <= i <= n - 1

其中 f(n) 是购买长度为 n 的杆的最低价格。使用记忆化，这可以在 O(n^2) 中计算。