The rod cutting problem is described in section 15.1 of the book “Introduction to algorithms” by Carmen et.al. We are given an array, p where p[j] represents the money we’ll get for a rod of length j. Given a rod of length n, what is the most money that can be made by cutting it optimally and selling the pieces?

The recurrence covered in the book which the solution is based on describes the dynamic programming array, x where x[j] represents the most money that can be made by cutting and selling a rod of length j. By taking the max across various choices of the first cut we get the recurrence:

x[n] = max(p[i] +x[n-i]); 0 <= i <= n

And then the solution is based on this.

Now, I asked this in an interview and the person came up with the following recurrence:

x[n] = max(x[i] +x[n-i]); 1 <= i <= n-1

I don’t see a good reason why this second recurrence won’t work. We can think of it as conditioning on there being a cut at position i. It does seem like the program we create will be less efficient than one based on the original recurrence.

Is there a way to quantify how much worse a program based on the second recurrence will be and why it might be a bad idea to use it?