Consider the rod-cutting problem, but in a different scenario. Suppose that every time we have to cut a rod, there is a cost proportional to the rod's length. For example, a rod of length 10, has an additional cost of 10, a rod of length 7 has cost 7 and so on.

We are given the length of the rod and the positions where the cuts have to be made, in order the get the maximum revenue. For example given length n = 10 and positions 2,4,7 we need to find the order in which the cuts have to me made in order to minimize the overhead cost that comes with the rod's length.

Devise recursive logic, and a recursive algorithm to solve this problem. Describe and explain the logic and the recursive algorithm. Ex-press and explain memoized version of the recursive algorithm. Express and explain a DP version of the algorithm. Explain how to do the traceback to actually find the order of the cuts given by the DP solution. Analyze the worst-case number of operations done by the DP algorithm. (This is not the number of cuts, but the number of computational operations done by the DP algorithm.)

So we want to figure out an order to do the cuts that minimizes the total cost of the cuts. For example, say in a rod of length 10, the desired cuts are at positions 2, 5, 9. If we do the cuts in left to right order, then we first lift a rod of length 10 (there is nothing we can do to avoid this), and create a rod of length 2 and another of length 8. Then we lift the rod of length 8, and cut so that two rods of length 3 and 5 are created. Then we lift the rod of length 5 and cut to create rods of lengths 4 and 1. So we lifted rods of length 10, 8, 5. But if instead we do the first cut at position 5, then the total lifts will be of length 10, 5 and 5, which is cheaper. You might think that the best policy is to first do the middle cut. But what is middle? Is it one that divides the rod into two roughly equal rods, or is it one that splits the number of cut-positions roughly evenly? So, it is not obvious that there is a simple strategy. Instead, we need an algorithm to find the best order to do the cuts.