![Problem 2 (25 pts] Prize Collecting Walks on a Grid
The input to this problem is an m x n grid. The top left entry is (1,1)
t](https://media.cheggcdn.com/media/0c4/0c4c6bfa-f64a-422b-b037-45a62a2c0a4f/phpM26mDw)
Problem 2 (25 pts] Prize Collecting Walks on a Grid The input to this problem is an m x n grid. The top left entry is (1,1) the bottom right entry is (m,n). Entry (i, j) in the grid contains a prize or penalty with known worth P(i,j) (the input). A walk starts at (1,1) and terminates at (m, n). At each step you can either move one unit to the right or one unit down or one unit to the right and one unit down. That is, from (i, j) you may move to either (i, j+1), (i+1, j) or (i +1, j +1) (if you are on the boundary and only one such neighbor exists, you must move to that existing neighbor). When you land on (k,r) you collect or pay money. How much you col- lect/pay depends on both P(k, r) and how you got to (k, r). If you move from (i,j) to (i+1,j) or (i, j +1) you will earn, respectively, Pli +1,j) or P(i, j +1). But, if you move to (i +1, j +1), you will earn P(i+1, j +1). The Value of a walk is the sum of all the prizes/penalties that you have collected/paid. Your goal is find the largest possible value walk. It is not necessary to find the walk itself; just the value. As an example, consider the grid and walk shown below a (1,1) 1.2) (1,5) 1,3) -8 (1.4) 1 (1,6) 7 -7 -4 2) (2,3) (2,4) 2,5) 2,6) 2.1) -2 12 -8 1 10 (3.1) 3.2) 3.3) 3,6) 3,5) 9 1 -27 -30 2 1 4.1) (4,2) (4.3) 10 4,5) 18 (4.6) 10 3 2 16 This walk has value 1 + {12+1+(-2) + 10 + 18 + 10 = 55 which is a max value walk. Design an O(mn) time dynamic programming algorithm for finding a maximum- value walk. (a) Give the recurrence upon which your DP algorithm is based. Before giving the recurrence, definc (using cnglish and math symbols) the meaning of each entry.
(b) Explain how, after filling in your table, you can use the information in your table to solve the problem. Note: This is meant to have a one line answer. Is the solution a particular table entry? If so, which entry? Or is it a function, e.g., the marimum, of a set of table entries? (c) Prove the correctness of the recurrence relation from part (a). (d) Give documented psuedocode for your algorithm. Your code only needs to find the value of a maximum-value walk, not the actual walk itself. (e) Explain why your algorithm runs in O(nm) time.
