Grid paths

Grid paths are a dynamic programming method for a grid where you move only right or down: it counts the paths from the top-left to the bottom-right cell, or finds the path with the largest or smallest sum. If moves can also go up or left, use BFS for the fewest steps or Dijkstra's algorithm for the cheapest path.

Explanation

A robot stands in the top-left cell of a 3 by 3 grid and moves one cell right or down at a time. How many paths lead it to the bottom-right cell?

Look at its last move: the robot enters the corner from the cell above or from the cell to the left. So the number of paths to a cell is the number for the cell above plus the number for the cell to the left. This is the staircase from the introduction to dynamic programming, with two ways in instead of two kinds of steps. A cell in the top row can only be entered from the left, so it gets the number of its left neighbour, and a cell in the left column gets the number above it. On an empty grid that is 1 all along both edges. Filling the grid row by row gives 6 paths to the corner.

Fig. 1. The number of paths to each cell of a 3 by 3 grid.

Now each cell of a 4 by 4 grid holds some coins, and the robot picks up the coins of every cell it passes, the first and the last included. The counting rule gives 20 paths on this grid. Which of them collects the most?

The natural move is to step, at each cell, to the neighbour with more coins. From the start the robot takes 2 over 1, keeps to the top row and then goes down the right edge. That is the red path in Fig. 2: 1 + 2 + 3 + 3 + 1 + 2 + 3 = 15. The blue path goes down through the 1 to the 5 and the 7: 1 + 1 + 5 + 7 + 5 + 2 + 3 = 24. A robot that looks one step ahead never sees the 5 and the 7 behind the cell with 1 coin.

Fig. 2. The red path collects 15 coins, the blue path 24.

Trying all 20 paths gives the right answer, but a 20 by 20 grid has 35,345,263,800 of them. Look at the last move again: say the best path enters the corner from above. Then the part before the last move is a path to the cell above, and it must be the best one there: a better one would make the whole path better. So the most coins on the way to a cell is its own coins plus the larger of two numbers, the most for the cell above and the most for the cell to the left. It is the counting rule with "the larger" in place of "the sum".

Write these numbers in a table the size of the grid, one per cell: a 20 by 20 grid needs only 400 of them. A cell needs the cell above it and the cell to its left, so we fill the rows from the top, each row from left to right. The top-left cell gets just its own coins, a cell in the top row reads only its left neighbour, and a cell in the left column only the one above. This is dynamic programming on a grid: each cell of the table is computed once from the cells a move can come from.

The top-left cell has 1 coin, so it gets 1.

The second cell of the top row can only be entered from the left: 1 + 2 = 3.

From the left again: 3 + 3 = 6.

6 + 3 = 9.

The first cell of the second row can only be entered from above: 1 + 1 = 2.

The larger of 3 above and 2 to the left is 3, and the cell has 2 coins: 3 + 2 = 5.

The larger of 6 above and 5 to the left is 6: 6 + 1 = 7.

The larger of 9 and 7 is 9: 9 + 1 = 10.

From above only: 2 + 5 = 7.

The cell in the third row, second column has 7 coins. The larger of 5 above and 7 to the left is 7, so it gets 14.

The larger of 7 and 14 is 14: 14 + 1 = 15.

The larger of 10 and 15 is 15: 15 + 2 = 17.

From above only: 7 + 3 = 10.

The larger of 14 above and 10 to the left is 14: 14 + 5 = 19.

The larger of 15 and 19 is 19: 19 + 2 = 21.

The larger of 17 above and 21 to the left is 21: 21 + 3 = 24. The robot can collect at most 24 coins.

To restore the path, start at the corner. Of 17 above and 21 to the left, 21 is larger, so the last move was right: R.

Of 15 above and 19 to the left, 19 is larger: R.

Of 14 above and 10 to the left, 14 is larger, so the move was down: D.

Of 5 above and 7 to the left, 7 is larger: R.

In the left column the move can only come from above: D.

From above again: D. The letters RRDRDD are the blue route read from the corner; reversed, DDRDRR.

1/22

Fig. 3. Step through the table with the buttons or the arrow keys. The outlined cells are the ones the new cell reads.

Blocked cells

The robot can't enter a blocked cell, so a blocked cell gets 0: no path ends there. Cells that can only be reached through a blocked cell then get 0 from the sum. An edge cell still copies its one neighbour, so the cell after a blocked cell in the top row gets 0, not 1.

Fig. 4. 7 paths reach the corner.

Implementation

The coins of cell (i, j) are a[i][j], and the table is f. Both are 2D vectors of long long, the 64-bit integer type, with n rows and m columns. Rows are numbered from 0 at the top, columns from 0 at the left.

1. State: f[i][j] is the largest sum of a path from the top-left cell to cell (i, j), both ends included.

2. Base case: f[0][0] = a[0][0].

3. Order: i from 0 to n - 1, and inside it j from 0 to m - 1.

4. Transition: f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]. In the top row only f[i][j - 1] exists, in the left column only f[i - 1][j]. On the coin grid, f[2][1] is the larger of f[1][1] = 5 and f[2][0] = 7, plus a[2][1] = 7, which gives 14.

5. Answer: f[n - 1][m - 1].

6. Restoring the path: from (n - 1, m - 1), step to the cell above or the cell to the left, whichever has the larger f, and write D or R. The larger one is where a best path came from; on a tie either works. Reverse the letters at the end.

For the smallest sum, replace max with min, and > with < when restoring the path. The input holds n and m, then n lines of m numbers; the program prints the largest sum and the path. For the coin grid the input is:

4 4
1 2 3 3
1 2 1 1
5 7 1 2
3 5 2 3

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> a(n, vector<long long>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> a[i][j];

    // state: f[i][j] = the largest sum of a path from (0, 0) to (i, j)
    vector<vector<long long>> f(n, vector<long long>(m));

    // order: row by row, each row from left to right
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) f[i][j] = a[0][0];                 // base case
            else if (i == 0) f[i][j] = f[i][j - 1] + a[i][j];        // top row: from the left
            else if (j == 0) f[i][j] = f[i - 1][j] + a[i][j];        // left column: from above
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];  // transition; min for the smallest sum
        }
    }

    // answer
    cout << f[n - 1][m - 1] << "\n";

    // restore the path; remove this block if you only need the sum
    string path;
    int i = n - 1, j = m - 1;
    while (i > 0 || j > 0) {
        if (j == 0 || (i > 0 && f[i - 1][j] > f[i][j - 1])) {   // < for the smallest sum
            path += 'D';
            i--;
        } else {
            path += 'R';
            j--;
        }
    }
    reverse(path.begin(), path.end());
    cout << path << "\n";
}

Each of the n \cdot m cells is computed from at most two others, so the time and the memory are $O(nm)$: they grow with the number of cells. If a move can also go diagonally down-right, the transition also reads the cell above-left, and the order stays the same.

Counting paths

To count, f[i][j] is the number of paths to (i, j). The base case is f[0][0] = 1, a blocked cell gets 0, and every other cell adds f[i - 1][j] and f[i][j - 1], whichever exist.

The input holds n and m, then n lines of . (free) and # (blocked), as for the grid of Fig. 4:

4 4
..#.
....
.#..
....

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];

    // state: f[i][j] = the number of paths from (0, 0) to (i, j)
    vector<vector<long long>> f(n, vector<long long>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '#') {        // blocked cell: no path ends here; checked first, so a blocked start gives 0
                f[i][j] = 0;
                continue;
            }
            if (i == 0 && j == 0) {      // base case
                f[i][j] = 1;
                continue;
            }
            if (i > 0) f[i][j] += f[i - 1][j];   // transition: from above
            if (j > 0) f[i][j] += f[i][j - 1];   // transition: from the left
            f[i][j] %= MOD;                       // remove if the problem asks for the exact count
        }
    }

    // answer
    cout << f[n - 1][m - 1] << "\n";
}

Correctness proof

Every number the table writes is the sum of a real path, so it is never more than the best. It is never less either: a best path enters the cell from above or from the left, and the part before is a path to that neighbour, so its sum is at most the neighbour's number. The table adds the cell's coins to the larger neighbour, so it gets at least the best path's sum (Fig. 5).

For counting, paths that enter a cell from above and paths that enter it from the left are different paths, and every path enters one way, so adding the two counts counts each path exactly once.

Fig. 5. From above, the corner would get 17 + 3 = 20; from the left, 21 + 3 = 24. The table keeps 24.

Common mistakes

• Filling the whole top row and left column with 1 before counting, so a cell after a blocked cell on the edge still gets 1: Fig. 4 then counts 8 paths instead of 7. Treat edge cells like the others, reading only the neighbour that exists.

• Padding the table with a border of zeros and taking the minimum, which then reads a 0 from outside the grid: on the coin grid the smallest sum is 11, but the padded table gives 9. Use explicit edge branches, or fill the border with a very large number such as 10^{18} (INF) for a minimum (-INF for a maximum when values can be negative).

• Filling in an order where a cell comes before the cells it reads, such as rows from the bottom up: on the coin grid that prints 13.

• Using a right-or-down table when moves go in all four directions. In Fig. 6 the cheapest path goes left along the middle row and costs 11, but the table finds only 15. No order then puts every cell after the cells it reads; use Dijkstra's algorithm.

Fig. 6. The blue path moves left and costs 11. The best right-or-down path costs 15.

Similar algorithms

Longest common subsequence and edit distance fill a table row by row too, but a cell is a pair of prefixes of two strings, and it also reads the cell above-left.

With no blocked cells, the count has a formula from binomial coefficients: a path is n - 1 moves down and m - 1 moves right in some order, so there are \binom{n+m-2}{n-1} paths. Use it when the grid is too big for a table, such as a million by a million, and the table when cells are blocked.

Practice