I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut problem".
Now, I have spent some time trying to understand it, but mostly trying to understand the pseudocode, and why it really works. I think dynamic programming is probably the most difficult design technique to put in practice that I have seen so far. The ideas are quite easy, but applying them is quite a nightmare, at least for me. You can choose between memoisation or a bottom-up approach, but you need to have a clear and deep understanding of the problem, and usually this requires quite a lot of time, but if you are in an exam...
From now on, I will assume that you know what the rod cut problem is.
Now, I wanted to create, based on a pseudocode from the book, an algorithm for the rod cutting problem that actually returns a list of the indices where we can find the small pieces that we have used to maximise the total price.
I have used Python, which simplifies quite a lot the process of writing programs, in general.
The following is the algorithm that I came up with (which is really similar to the pseudo code that the authors provide to find the maximum revenue for a rod of a certain length, but that algorithm does not calculate and returns which smaller pieces maximise the revenue):
def extended_bottom_up_rod_cut(prices, n): revenues = [-sys.maxsize] * (n + 1) s = [] * (n + 1) revenues = 0 s =  for i in range(1, n + 1): max_revenue = -sys.maxsize # a big small number for j in range(1, i + 1): # Note that j + (i - j) = i. # What does this mean, or why should this fact be useful? # Note that at each iteration of the outer loop, # we are trying to find the max_revenue for a rod of length i # (and we want also to find which items we are including to obtain that max_revenue). # To obtain a rod of size i, we need at least 2 other smaller rods, # unless we do not cut the rod. # Now, to obtain a rod of length i, # we need to put together a rod of length j < i and a rod of length i - j < j, # because j + (i - j) = i, as we stated at the beginning. if max_revenue < prices[j] + revenues[i - j]: max_revenue = prices[j] + revenues[i - j] if prices[i - j] != 0: s[i] = [j, i - j] # Indices of prices such that price[j] + price[i - j] = max_revenue of i else: s[i] = [j] revenues[i] = max_revenue return revenues, s
First of all, is the algorithm correct?
Apparently, it seems that it returns the right answer, but I am a bit confused: as the size of the rod increases, we are always going to just use at most 2 small pieces, and no more than that, but why such an algorithm should give the right answer? Why using 3 or more pieces would not give the right answer?