Moving in a Grid Imagine that you are placed on a grid with n spaces in every row and n spaces in every column. You can start anywhere along the bottom row of the grid, and you must move to the top row of the grid. Each time you move, you can either move directly up (staying in the same column, but moving up a row), up and to the left (moving over one column and up one row), or up and to the right (moving over one column and up one row). You cannot move up and to the left if you are in the leftmost row, and you cannot move up and to the right if you are in the right most row. Each time you move, you are either paid or pay; that is, every legal move from square x to square y is assigned a real value p(x, y). Sure, p(x, y) can also be 0.

Give a dynamic programming algorithm to compute your sequence of moves to receive the maximum payoff to move from the bottom of the grid to the top of the grid. (Your maximum payoff may be negative.) You must calculate the value of the optimal solution (i. e., the payoff) and the solution itself (i. e., the sequence of moves). Again, you can start at any square in the bottom row and end in any square in the top row.