Dynamic Programming - Rod Cutting

Question

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 only 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,

Answer 1

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.