DP on a Grid
GOALCount paths across a two-dimensional grid.
Moving only RIGHT or DOWN, how many paths cross a grid from the top-left to the bottom-right? It is the same idea as one-dimensional DP with one more dimension: you reach a cell either from the left or from above.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
using namespace std;
int main() {
int rows = 3, cols = 4;
vector<vector<long long>> paths(rows, vector<long long>(cols, 0));
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (r == 0 && c == 0) {
paths[r][c] = 1;
} else {
long long fromUp = (r > 0) ? paths[r - 1][c] : 0;
long long fromLeft = (c > 0) ? paths[r][c - 1] : 0;
paths[r][c] = fromUp + fromLeft;
}
}
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) cout << paths[r][c] << " ";
cout << endl;
}
return 0;
}1 1 1 1 1 2 3 4 1 3 6 10
//LINE BY LINE
Watch it run
A 3 by 4 grid. Top-left corner to bottom-right corner.
Adding walls
Most variations of grid DP add "some cells cannot be entered". The change to the code is one line.
if (blocked[r][c]) {
paths[r][c] = 0; // no route can pass through here
} else {
paths[r][c] = fromUp + fromLeft;
}Setting 0 means "no route reaches here". As later cells add it in, the zero spreads by itself and the whole blocked region becomes unreachable.
For a cheapest-path variant, take the min instead of adding, start the first cell at 0 and unreachable cells at a very large number.
The first row and the first column
Cells in the first row have nothing above them, and the first column nothing to the left. Filling those separately, before the main loop, is the clearest way.
for (int c = 0; c < w; c++) paths[0][c] = 1; // only one way along the top
for (int r = 0; r < h; r++) paths[r][0] = 1; // only one way down the side
for (int r = 1; r < h; r++)
for (int c = 1; c < w; c++)
paths[r][c] = paths[r-1][c] + paths[r][c-1];The other trick is to make the table one row and one column bigger and leave that extra edge at zero. Then you need no if at all.