Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question
1  
There are $n-1$ potential cutting points. For each point you face a binary choice: "to cut or not to cut - that is the question". –  Jyrki Lahtonen Aug 31 '12 at 12:37
    
@JyrkiLahtonen I see . thanks . –  Geek Aug 31 '12 at 12:39

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.