1. Assume there is a game played by moving a small stone on a 2xn chessboard such that there are numbers written in the cells of the chessboard indicating the amount of points you earn when you place the stone the corresponding cell. You initially place the stone one of the cells in the first column, and at each step, you move it to one of the cells in the right hand column. You end the game when you move the stone one of the cells in the rightmost column. Note that if you move the stone to the other row, you loose 3 points. Your task is to design a dynamic programming algorithm that takes a 2xn integer matrix as input, and computes the maximum amount of points that can be earned In the following instance, if the shaded path is followed, (2+7 3+3+9 3) points will be earned. 5 7 3 7 282 9 a) (15p) Define a subproblem, construct the recurrence relation, and identify base case(s) b) (15p) Use your student number as the input, and build a table for the solutions of the subproblems on your input Assume your id is 14290519. The corresponding input matrix will be 05 1 9 9 The table for the input will be as follows: OPT(j) 5 6 Note that for this example, I just filled two entries. But you must fill all the entries in the corresponding table