Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
up vote 6 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|cite|improve this answer

Your Answer


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.