如果我以不同的长度切割一根杆，我如何得到总结果数为2 ^（n-1）？其中n是杆的长度

Question

在Cormen的“动态编程”部分中，讨论了杆切割问题。我不知道如何得到2 ^（n-1），因为我们可以用不同的方法切割长度为n的杆。

希望有人可以对此有所了解。

Answer 1

考虑杆的长度为'n'米。在每个仪表上，您都有两种选择，可以选择是否切割。因此，乘以每米的可能性，您会得到2 ^（n-1），因为存在内部n-1个切割点。