Suppose you have a rod of length N, and you want to cut up the rod and sell the pieces in a way that maximizes the total amount of money you get. A piece of length i is worth pi dollars. Devise a Dynamic Programming algorithm to determine the maximum amount of money you can get by cutting the rod strategically and selling the cut pieces. a. Define (in plain English) subproblems to be solved. b. Write a recurrence relation for the subproblems c. Using the recurrence formula in part b, write pseudocode to find the solution. d. Make sure you specify i. base cases and their values ii. where the final answer can be found e. What is the complexity of your solution