Hey folks,

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 we stop using 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,