title: Dynamic Programming - Rod Cutting
body: <p>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.</p>
  
  <p>The classic bottom-up solution for this is the following:</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>1 + 3
  2 + 2
  3 + 1
  4 + 0
  </code></pre>
  
  <p>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).</p>
  
  <pre><code>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]
  </code></pre>
  
  <p>Does anyone see something wrong with this approach?</p>
  
  <p>Thanks,</p>