You are given a checkerboard with n rows and n columns. This is just a nn table V . The (i; j) entry of V has value v(i; j) (can be positive or negative). We want to move a checker from the top-left corner (i.e., position (1; 1)) to the bottom-right (i.e., position (n; n)). The only legal moves are to move a checker down by one square, right by one square, or diagonally down-right by one square. The value of a sequence of moves is the sum of the values of the entries in the sequence. We want the maximum value of any legal sequence of moves. Here is an example of a 3 3 checkerboard: