This answer isn't really helpful for your assignment and isn't framed in terms of dynamic programming. It's just about solving the problem fast.
This problem can be solved in $O(n \lg^2 n)$ time by using iterative max-convolution on the prices.
Max-convolution takes an array $a$ and tells you $\max_j^d (a_j + a_{d-j})$ for each starting offset $d$. By being clever you can do it in $O(n \lg n)$ time instead of $O(n^2)$, kinda reminiscent of the convolution theorem.
edit: but see @Kaban-5's important caveat in the comments, about this algorithm depending on random inputs instead of random choices!
The key thing to realize is that, if the price for a piece of length $d$ is less than the price of a piece of length $d-j$ plus a piece of length $j$, then the effective price for a piece of length $d$ should increase to the sum of those two prices. And if we keep looking for these pricing inefficiencies and fixing them, we'll converge on the true optimal selling price for each length.
A single max-convolution will replace every price with the maximum you can get by splitting a piece into up to two pieces and selling all the pieces. A second max-convolution will be searching through all splits into up to 4 pieces. The third goes up to 8. And so forth until we hit up-to-$n$ after the $\lg n$'th max-convolution.
Here's the algorithm:
def bestSplitPrice(prices):
"""
Assuming you have a piece of yarn of length len(prices)+1, find
the best price you can get by cutting it and selling the pieces
at the given prices-per-length.
"""
prices = [0] + prices #A zero-length piece costs nothing
for i in range(ceil(lg2(prices))):
prices = max_convolve(prices, prices)[:len(prices)]
return prices[-1]
And here's an example:
prices = {1:1$, 2:3$, 3:3$, 4:4$, 5:5$, 6:5$, 7:7$}
# array-ify, including 0-length price
prices = [0, 1, 3, 3, 4, 5, 5, 7]
# max-convolve lg2(8) = 3 times
prices = [0, 1, 3, 4, 6, 6, 7, 8]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
The best piece-price for length-7 is 10$
Here's how the max-convolutions play out if only the 1$ piece is given a price:
prices = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
prices = [0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
prices = [0, 1, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 7]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]
Notes:
- I suspect this can be cut to $O(n \lg n)$ by having the max-convolutions double-hitting exponentially larger and larger sections of the array.