What is the formal justification for the correctness of the second formulation of rod cutting DP solution

Question

CLRS on section 15.1 3rd edition has a good discussion of the rod cutting problem. I will add a description at the end of the question for reference.

Define $r_j$ to be the optimal way to cut a rod of integer length $j$. Since we do not know where is the optimal place to cut the rod we consider every location $ i \in \{0,\cdots,j\}$ (essentially doing exhaustive search) to do the cut. Then we are left with two rods of length $i$ and $j-i$ to cut optimally. If we consider every location we could do a cut and then cut the remaining rods optimally, then we have essentially solved $r_j$ optimally. i.e. we get the following recursion:

$$ r_j = \max \{p_n, r_1 + r_{k-1}, r_2 +r_{j-2}, ..., r_{j-1} + r_1 \}$$

However there seems to be an alternative (or maybe simpler strategy to solve such a problem):

$$r_n = \max_{1 \leq i \leq n} \{ p_i + r_{n-i} \}$$

CLRS has the following discussion about it:

In a related, but slightly simpler, way to arrange a recursive structure for the rod- cutting problem, we view a decomposition as consisting of a first piece of length $i$ cut off the left-hand end, and then a right-hand remainder of length $n -i$. Only the remainder, and not the first piece, may be further divided. We may view every decomposition of a length-n rod in this way: as a first piece followed by some decomposition of the remainder. When doing so, we can couch the solution with no cuts at all as saying that the first piece has size $i = n$ and revenue $p_j$ and that the remainder has size $0$ with corresponding revenue $r_0 = 0$. In this formulation, an optimal solution embodies the solution to only one related subproblem-the remainder-rather than two.

Personally I've always found it harder to convince myself that this in fact optimal (and that is therefore equivalent to the first one). Therefore I was wondering if anyone had a good argument or maybe a good formal proof to arguing why this second formulation is in fact optimal.

Usually I've tried to justify it to myself by having the following thought experiment: well, if I want to have an optimal revenue I need to make sure that I some how explore all good solutions exhaustively and not miss any. If I want the solution to the whole thing $r_j$ then it could be that the full rod is required, then the cut is at position $i=n$. That is if the optimal solution contains no cuts. But if we have a cut we will have some part of the rod that must remain un cut. If that is the case, then just consider all possible full parts of the rod from the beginning of the rod to the end that remain uncut. Basically, it seems that the solution is as follow, every solution to $r_j$ must contain a piece of rod from the beginning that is uncut to some cutting location $i$. Since this is part of the optimal solution, we just consider all beginnings that are "full" rods up to $i$ and then make sure to solve the remaining optimally. This justification feels close to being the argument of correctness but for some reason it just seems to be missing something (wish I knew what it was).

Does someone know how to write a better clear proof of correctness of this? If its really formal or rigorous that is ok with me, I just sort of want some proof for the second recursion where there is no doubt that its correct.

Thanks for the help!

---

Recall the rod cutting problem. You manufacture steel rods of some fixed length and sell them in segments of integer length and because of the laws of supply and demand, the price per length is not constant. Given a set of prices (i.e. an array $p_i$ indicating the price for an integer cut of length $i$) for each possible length segment, how should you cut a given rod of length $n$ into integer length segments to maximize revenue? You may assume that no cost or loss incurred with each cut.

Answer 1

The proof of $r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$ is divided into two parts. In the first part, we prove that $r_n \geq \max_{1 \leq i \leq n} (p_i + r_{n-i})$. In the second part, we prove that $r_n \leq \max_{1 \leq i \leq n} (p_i + r_{n-i})$.

First part. It suffices to prove that for each $1 \leq i \leq n$, $r_n \geq p_i + r_{n-i}$. Indeed, consider first breaking the rod into a piece of size $i$ and a piece of size $n-i$, and then cutting the second piece optimally. This strategy guarantees a profit of $p_i + r_{n-i}$.

Second part. It suffices to prove that for some $1 \leq i \leq n$, $r_n \leq p_i + r_{n-i}$. Consider any way of cutting the rod. Let $i$ be the size of the leftmost piece, which results in a profit of $p_i$. The other pieces (if any), put together, form a rod of size $n-i$, and so the profit gained from them is at most $r_{n-i}$. In total, the profit is at most $p_i + r_{n-i}$. In particular, the optimal profit $p_n$ is at most $p_i + r_{n-i}$.

Answer 2

Let's assume the optimal cut for 8 is: $8 = 1+2+3+2$.

When $i=3$, it means you cut at length 3, and leave 5 as a second part.

You can get the optimal value from $r_3$ and $r_5$, of course.

But please be noted, you must have already get this optimal value when $i=1$. When $i=1$, $r_8 = r_1 + r_7$, where $r_7$ can give you optimal cut as $7 = 2+3+2$.

Therefore, to avoid redundant re-calculation as above, keeping one side uncut, and try to find the best cut at the other side is the best solution.