In the rod cutting example we discussed in class, given a rod of length n and a table pi of prices for i =1, 2, ..., n, we used rn to represent the optimal revenue obtainable given a rod of length n. We express rn using the
recurrence: rn = max{pi + rn−i : 1 ≤i ≤n}.
Consider a variant of this problem where a fixed cost c is associated with making each cut, please answer the following questions. Thus, the revenue becomes the total prices of all cut rods minus the total costs associated with making the cuts.
(a) What is the recurrence for the new problem?
(b) Please provide pseudocode for a dynamic programming algorithm that uses the bottom-up method.
(c) Please provide pseudocode for a dynamic programming algorithm that uses the top-down with mem-oization approach.