You find yourself curiously stranded on a n by n mysterious grid (shown below), unsure of how you got there, or how to leave. You denote the rows of the grid from bottom to top as 1, 2, ..., n, and similarly denote the columns from left to right as 1, 2, ..., n. Cell (i, j) refers to row i, column j. You are currently standing at the bottom-left corner of the grid and wonder to yourself how many different ways there are to walk to the top-right corner of the grid. However, there are certain conditions on the grid's cells. In the normal cells of the grid (cells with white background below), you feel fatigued and are only able to move to the cell to the immediate right (to the next column). In the special cells of the grid (cells with blue background below), you feel more energised and are able to move either to the cell that is immediately up (to the next row) or immediately right (to the next column).
Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Question

You find yourself curiously stranded on a n by n mysterious grid (shown below), unsure of how you got there, or how to leave. You denote the rows of the grid from bottom to top as 1, 2, ..., n, and similarly denote the columns from left to right as 1, 2, ..., n. Cell (i, j) refers to row i, column j. You are currently standing at the bottom-left corner of the grid and wonder to yourself how many different ways there are to walk to the top-right corner of the grid. However, there are certain conditions on the grid's cells. In the normal cells of the grid (cells with white background below), you feel fatigued and are only able to move to the cell to the immediate right (to the next column). In the special cells of the grid (cells with blue background below), you feel more energised and are able to move either to the cell that is immediately up (to the next row) or immediately right (to the next column).  
 Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Accepted Answer