Question 1 (Cherry Picking, Dynamic Programming) It is the cherry pick- ing season! You are going into a cherry field and you want to maximize the amount of cherries you pick. The field is organized into a two-dimensional grid of dimensions mxn where each grid cell represents a plot as shown in the figure below. Enter from any cell on the north + + + + 2 1 2 3 4 5 n= 6 i 1 7 15 1 12 5 Allowed moves 2 10 6 5 10 4 s 8 SE 3 4 5 10 13 4 15 4 3 8 2 17 17 A. North m = 5 11 14 8 12 5 3 Erit from any cell on the south + 1 + + + optimal path Each plot contains a number which represents the amount of cherries in that plot in pounds. You can enter the field at any point on the north side and erit at any point on the south side. At each step, you are allowed to move in one of three directions, southwest, south, or southeast. You can collect all the cherries in each plot you visit. Your goal is to find the path that marimizes the amount of cherries you pick. For example, the best path for the above problem is highlighted on the figure and will result in collecting a total of 64 pounds of cherries. We will use dynamic programming to solve this problem. To do that, we would like to derive a recurrence formula Pij that represents the marimum amount of cherries we can pick after we reach and collect the plot at row i and column j. We can represent the recurrence formula as follows. base case Pij = ;base case condition ; otherwise recurrence case 1. (2 points) Write down the base case and base case condition of the recur- rence relation 2. (3 points) Write down the recurrence case of the recurrence relation. 3. (2 points) Which value of the recurrence relation represents the final an- swer of the problem? In other words, which entry in the table (i, j) will contain the final answer. 4. (5 points) Write down a bottom-up iterative algorithm based on your re- currence relation that finds the marimum amount of cherries to pick. You do not have to produce the path in this part. 5. (1 point) What is running time of your algorithm? 6. (3 points) Use your bottom-up algorithm to answer the problem given above and highlight the optimal answer. Keep in mind that, like all optimization problems, there might be more than one optimal answer but they should all have the same final value. 7. (5 points) (Bonus) Update your algorithm to produce the optimal path as a sequence of plot locations, in addition to the final value