Simpler recurrence of Dynamic Programming Rod-cutting

Question

In CLRS, the recurrence solution to the rod cutting problem is:

r_n = max (p_n, r₁+r_n-1,...,r_n-1+r₁)

This recurrence is pretty clear and I understood it.

However, I am facing difficulty in understanding the simpler version of this recurrence provided in the book, which is:

r_n = max_1<=i<=n(p_i + r_n-i) , where p_i is the cost of piece of length i.

I don't understand, how this recurrence is similar to the first recurrence. To me the second recurrence may miss the optimal solution as we are not considering the optimal cost of first cut (we are simply taking it's normal price).

Shouldn't we always consider the optimize cost of the both sides like the first equation?

Answer 1

Here is the reasoning.

An optimal cut must include a piece of some length i. That piece will be sold for price pi. You will then cut the rest of the rod into other pieces, and can do no better than to cut it optimally.

Therefore we just need to find ONE of the pieces in the cut. Recursion will take care of figuring out the rest.

And that is exactly what the simpler recurrence does.

Answer 2

Though this reply is late. I anyway thought of posting it because I got confused along the same lines.

I think the confusion arises when we think of both formulas to be replacement of the other. Though they count the same phenomena, it is done in two different ways:

Let, B(i) = optimal price for cutting a rod of length i units and p(i) = price of a rod of length i units.

Formula 1: B(i) = max(1<=k<=floor(i/2)) {B(k) + B(i-k)} and P(i)

Formula 2: B(i) = max(1<=k<=i) {p(k) + B(i-k)})

Consider a rod of length 4, it can be cut in the following ways :

1) uncut of length 4

2) 3, 1

3) 2, 2

4) 2, 1, 1

5) 1, 3

6) 1, 2, 1

7) 1, 1, 2

8) 1, 1, 1, 1

According to Formula 1:

option 1 corresponds to P(4)

option 2,5,6,7,8 corresponds to B(1) + B(3)

option 3,4,6,7,8 corresponds to B(2) + B(2)

According to Formula 2:

option 1 corresponds to P(4)

option 2 corresponds to P(3) + B(1)

option 3,4 corresponds to P(2) + B(2)

option 5,6,7,8 corresponds to P(1) + B(3)

So to conclude, 1 and 2 are counting the optimal solution but in different ways, where 2 is more compact and makes lesser recursive calls compared to 1.

Answer 3

In addition to the explanations given by the others, I would like to point out that the second recursion actually eliminates the common rod cutting sub-problems, such as the rutting a rod of size n=4 at either position i=1 or i=3, i.e., cutting off a one-unit piece from either end.