algorithm - 如果我切割不同长度的杆，我如何获得 2^(n-1) 的结果总数？其中 n 是杆的长度

Question

在 Cormen 的动态规划部分中，讨论了杆切割问题。我无法理解我们如何得到 2^(n-1) 作为我们可以切割 n 长度杆的不同方式的总数。

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

标签： algorithmdynamic-programmingcombinatorics

Answer 1

考虑杆是'n'米。在每一米，你有两种可能性，要么剪掉它，要么不剪掉它。因此，在每米乘以 2^(n-1) 的可能性，因为有 n-1 个内部切割点。