438. The Best Way to Cut the Rod
A rod of length n can be cut into whole-number pieces. A piece of length k
sells for price[k]. Print the greatest total revenue, cutting as many times as
you like or not at all.
n = 4, prices for lengths 1..4 = 1 5 8 9 -> 10 two pieces of length 2
Note the answer beats selling the whole rod for 9, and also beats the best price-per-unit piece taken greedily.
This is UNBOUNDED: each length may be used any number of times, since cutting a piece of length 2 does not use up the possibility of another.
dp[0] = 0
dp[L] = max over k in 1..L of price[k] + dp[L - k]
The direction of the loops is the point of putting this problem here. Filling
L upwards and trying every first cut k lets dp[L - k] already include more
pieces of the same length, which is exactly what unbounded means.
Compare problem 439, where each item may be used at most once, and the sweep must run the other way to forbid reuse. The two are adjacent deliberately: each is wrong with the other's loop direction, and knowing which is which is the most reused fact in this topic.
Constraints - `1 ≤ n ≤ 2000` - `0 ≤ price ≤ 100000`
Input
The first line contains an integer n.
The second line contains n space-separated prices, for lengths 1 to n in order.
Output
Print the greatest total revenue obtainable from the rod.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.