Dynamic Programming - Rod Cutting

I was looking at the CLRS the other day just to refresh my mind a little bit and bumped into the classic rod cutting problem.

The classic bottom-up solution for this is the following:

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = -1
5:    for i = 1 to j
6:       q = max(q, p[i] + r[j-i])
7:    r[j] = q
8: return r[n]

Now there is something I keep thinking about. Why do we keep reusing p[i] on L.6? I mean let's say we have j = 4 then it would compute the following combinations:

1 + 3
2 + 2
3 + 1
4 + 0

what's the point of computing "3 + 1" twice really. What I am suggesting is not to use p[] and o开发者_JAVA技巧nly use r[] and stop at floor(j/2).

1: let r[0..n] be a new array
2: r[0] = 0
3: for j = 1 to n
4:    q = p[j]
5:    for i = 1 to floor(j/2)
6:       q = max(q, r[i] + r[j-i])
7:    r[j] = q
8: return r[n]

Does anyone see something wrong with this approach?

Thanks,

There isn't anything wrong with your optimization. I've seen it used/mentioned several times before in the rod cutting problem (here's just one example: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec09.349.pdf). There's no such thing as a perfect textbook. It might have been either a mistake on CLRS's part, or they just felt that mentioning such optimizations would have cluttered the book.

Typically such introductory books will focus on high level concepts and leave finding such trivial optimizations up to the reader. Consider bubble-sort: not everyone would mention the fact the simple optimization that the inner loop j only has to go up to i.

I know this is an old question, but I feel the question was only half-answered. To answer the first part of your question:

what's the point of computing "3 + 1" twice really

I wanted to point out that there is a footnote in the book that states,

If we required the pieces to be cut in order of nondecreasing size, there would be fewer ways to consider. For n = 4, we would consider only 5 such ways. [...] We shall not pursue this line of inquiry further, however.

There's nothing wrong with your optimization. I think it was purposely excluded from the book to make ensuing exercises easier for students to solve.

your optimization is good. There is a much more efficient way of doing this with a single loop instead of 2 loops :

1: let r[0..n] be a new array
2: r[0] = 0
3: q=-1
4: for j = 1 to floor(n/2)
5: q = max(q, r[j] + r[n-j])
6: r[j] = q
7: return r[floor(n/2)]