Dynamic programming

1. This question is about dynamic programming. You are given a pole of length n>0, which can be cut into any number of smaller poles. The value of a pole of length i is given by v(i), according to the following table: Length value vi) 1 3 2 5 3 11 4 14 5 16 6 19 7 20 8 24 9 28 10 28 The maximum revenue r(i) for a pole of length i is the maximum amount of value that can be achieved from the pole, perhaps by cutting it into pieces and summing the values of the pieces (a) What is the maximum revenue for a pole of length 2? [2 marks] (b) What is the maximum revenue for a pole of length 3? [2 marks] (c) Give a recurrence relation that gives the maximum revenue r(k) in terms of smaller sub-problems, or as a base case. (8 marks] (d) Using your recurrence relation from part (c), calculate the table needed to find r(10), the maximum revenue for a pole of length 10 [10 marks] (e) What length pieces could a pole of length 10 be cut into to obtain the maximum revenue? Give one solution that leads to the maximum revenue. [3 marks)