9. Given n balloons, indexed from 0 to n1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If you burst balloon i you will get nums [left]nums[i] nums [ right ] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. You may assume nums [1]=nums[n]=1 and they are not real therefore you can not burst them. Design an dynamic programming algorithm to find the maximum coins you can collect by bursting the balloons wisely. Here is an example. If you have the nums array equals [3,1,5,8]. The optimal solution would be 167 , where you burst balloons in the order of 1,5 3 and 8 . The left balloons after each step is: [3,1,5,8][3,5,8][3,8][8][] And the coins you get equals: 167=315+358+138+181. 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