Problem Statement 

---

The rod-cutting problem is the following. Given a rod of length `n` inches and a table of prices `Pi` for `i = 1, 2, 3,....n`, determine the maximum revenue `Rn` obtain- able by cutting up the rod and selling the pieces. Note that if the price `Pn` for a rod of length `n` is large enough, an optimal solution may require no cutting at all.

Consider the case when`n=4`. Figure shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue `P2+P2=5+5=10`, which is optimal.

[![enter image description here](https://i.stack.imgur.com/Yy1Gi.png)](https://i.stack.imgur.com/Yy1Gi.png)

The below code is a bottom-up approach of building the solution for rod-cutting.

```
for (i = 1; i<=n; i++)
{
   int q = INT_MIN;
   for (j = 0; j < i; j++)
       q= max(q, p[j] + r[i-j-1]);
   r[i] = q;
}
return val[n];

```

Why do we need an auxiliary array `r[n+1]`? Couldn't the problem be solved only by using just array `p`? Is it used because we cannot access p[-1] when we are cutting of rod length n and 0?
Why are we using `q = max(q, p[j] + r[i-j-1])` when p is not updated to new values?