Help me solve this dynamic programming (rod-cutting, optimization) problem:

2. (Minimarts) You are managing the construction of minimarts along a stretch of road. The possible sites for the minimarts are given by real numbers Tn, each of which specifies the position along the road measured in miles from its beginning. Assume that the road is a straight line. If you place a minimart at location i, your company wl make a profit of ri 0 dollars Regulations require that every pair of minimarts be at least 5 miles apart. You'd like to place minimarts at a subset of the sites so as to maximize total profit, subject to this restriction The input is given as a list of n pairs (z,),..., (zn, n) where the ri's are sorted in increasing order (a) You first consider some very simple approaches to the problem, which you realize will not work well. For each of the following approaches, give an example of an input on which the approach does not find the optimal solution i. Next available location: put a minimart at i = 1 . From then on, put a minimart at the smallest index i which is more than five miles from your most recently placed minimart ii. Most profitable first: Put a minimart at the most profitable location. From then on, place a minimart at the most profitable location not ruled out by your current minimarts. (b) Give a dynamic programming algorithm for this problem. Analyze the time complexity of your algorithm. To make it easier to present your answer clearly, follow the steps below: i. Clearly define the subproblems that you will solve recursively. ii. Give a recursive formula for the solution to a given subproblem in terms of smaller iii. Give a bottom-up pse iv. Give pseudocode for an algorithm that uses the information computed in the pre- subproblems. Explain why the formula is correct optimal solution. Analyze the time complexity of your algorithm vious part to output an optimal solution. Analyze the time complexity of your udocode for an algorithm that calculates the profit of the algorithnm