棒切割动态规划

-1

在CLRS算法导论，引入动态规划期间杆切割问题，有一段说棒切割动态规划

在一个相关的，但稍微简单，方式为切割问题安排递归结构，我们将分解看作为，其由第一段长度和第二段长度组成，然后是长度为n-i的右侧余数。只有剩余部分，而不是第一部分，可能会进一步划分。

为什么我们不需要考虑第一段长度的分解我切断了左端？

谢谢。

来源

2017-03-05 Ames ISU

-1，对不起。没有解释“引入动态编程期间的切割杆问题”是什么，你的问题就没有意义了。实际上，我现在恰好有一本* Introduction to Algorithms *，但期望每个人都会这么做是不合理的。 – ruakh

（附录：我现在已经拿出了我的副本，但我找不到有问题的问题，我怀疑你的版本与我的版本不同。） – ruakh

切断左端的杆的长度是切成所需长度的部分 - 右侧部分的使用尚未确定，可能会切成较小的部分。

来源

2017-03-05 01:47:09

为什么需要第一块的长度？根据描述，是否分解第一块应该给出相同的结果，这意味着DP将遍历所有可能性，但似乎并不明显。 –

@AmesISU有一个最佳分解。这种最佳分解将具有一定规模的第一块。如果我们搜索所有可能的第一部分组合和其余部分的最优分解，我们将*找到最优分解。把它看作是对房间的完整搜索。您通过将房间分成几个部分然后完全搜索每个部分进行搜索。搜索一个部分时，您不必担心它*可能*在其他地方。你的搜索模式将最终覆盖这种可能性。 – btilly

棒切割动态规划

回答

相关问题