Design a dynamic programming solution for the following problem. You have a board consisting of n rows and m columns of cells. Some, but not necessarily all, of the cells have pebbles in them (at most one pebble per cell). A robot starts at the top left cell and is supposed to move to the bottom right cell. At each step, the robot can either move down by one cell or to the right by one cell. When the robot is in a cell with a pebble, it collects the pebble. What is the maximum number of pebbles the robot can collect? (The locations of the pebbles are known.) Hint: For arbitrary i and j, let F[i,j] be the maximum number of pebbles the robot can collect when traveling between its starting location and cell (i,j). The robot can get to cell (i,j) in one of two ways: either from the cell above or from the cell to the left. Use boolean variable p ij to indicate whether or not there is a pebble in cell (i,j).

(a) Which element(s) of F hold, or are needed to compute, the nal answer?

(b) Which element(s) of F hold the basis element(s) and how should they be lled in?

(c) What is the formula for lling in each of the other (non-basis) elements of F?

(d) In what order should the elements of F be lled in?

(e) What is the running time of the algorithm and why?

(f) How can the actual optimal path be determined? (Just give a brief high-level description.)