'Recursive Solution for Rod Cutting problem - dynamic programming
Problem Statement: Given a rod of length n inches and an array of
prices that includes prices of all pieces of size smaller than n.
Determine the maximum value obtainable by cutting up the rod and
selling the pieces.
For this problem, I am confused as to why everywhere I see the solution to this problem i.e. the maximum value of the Rod defined as
R[n] = Max (p[n], R[n-1] + P[1], R[n-2] + P[2] + ... P[1] + R[n-1] --- 1
and not as
R[n] = Max (p[n], R[n-1] + R[1], R[n-2] + R[2] + ... R[1] + R[n-1] --- 2
where R[n] means the maximum revenue that we can get by selling n rods.
Base case as:
R[0] = some value
R[1] = somevalue
The eq 2 is more correct and apt because at no point R[i] will ever be less than P[i].
What am I missing?
Solution 1:[1]
Both equations give the same answer. In that sense none of them is more correct than the other. It is a matter of taste which one you prefer. I found eq 1 a bit more intuitive. The solution is the maximum of taking the whole rod, or cutting off a piece of length 1 and do the best with the rest, or cutting off a piece of length 2 and do the best with the rest, ...
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Henry |
