3
$\begingroup$

Basically I am trying to understand the concept of dynamic programming via Rod Cutting example.

How the number of ways in which a rod of length $n$ units can be cut is ${2}^{n-1}$ and not $2^n$?

Consider the smallest cut be of one unit and there can also be a case where there is no cut at all .

  • 0
    @JyrkiLahtonen I see . thanks .2012-08-31

1 Answers 1

8

I take it you are only allowed to cut the rod into integer lengths. I don't know about dynamic programming, but if you mark all the places where you are allowed to cut the rod, there are $n-1$ of them, and at each of those $n-1$ places, either you cut, or you don't, making, all told, $2^{n-1}$ different ways to cut.

  • 1
    @vij, it's based on the multiplication formula. If you have to perform $k$ tasks, and you can perform the first task in $a_1$ different ways, and no matter how you do the first task, you can do the second task in $a_2$ different ways, and so on, and so forth, then you can do the whole job in $a_1a_2\cdots a_k$ ways.2017-02-01