Step 3 of 6

Paths through a grid

Many DP tables are two-dimensional. A robot starts in the top-left corner of a grid and may only move right or down. How many different routes reach the bottom-right corner?

The last move into any cell came either from the cell above it or from the cell to its left, so:

paths[r][c] = paths[r - 1][c] + paths[r][c - 1]

The top row and the left column have exactly one route each (straight along the edge). Filling the table row by row, left to right, guarantees the cell above and the cell to the left are already done:

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    int rows = 3, cols = 4;
    std::vector<std::vector<long long>> paths(rows, std::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;                  // along an edge
            else paths[r][c] = paths[r - 1][c] + paths[r][c - 1];   // from above + from the left
        }
    }
    for (const auto& row : paths) {
        for (long long v : row) std::cout << std::setw(3) << v;
        std::cout << "\n";
    }
    std::cout << "routes: " << paths[rows - 1][cols - 1] << "\n";
}

  1  1  1  1
  1  2  3  4
  1  3  6 10
routes: 10

Compare this with the backtracking module, where following every path one by one took time proportional to the number of paths. A 30 × 30 grid has over 30 quadrillion right/down routes; listing them would take years, but the table has only 900 cells, and each one takes a single addition.

Obstacles and costs

Two common variations use the same table:

• Blocked cells: a wall has 0 routes through it. The edge rule changes too: a cell on the top row can only be reached from its left, so once a wall appears on an edge, every cell after it along that edge has 0 routes.
• Cheapest path: each cell has a cost, and you want the smallest total cost of a right/down path. Replace "add the two neighbors" with "take the cheaper neighbor, plus this cell's cost": best[r][c] = cost[r][c] + min(best[r - 1][c], best[r][c - 1]). On the edges, there's only one neighbor to take.

Your task

Write count_paths(grid), counting right/down routes from the top-left to the bottom-right cell that avoid # walls (0 if the start or end is a wall), and min_path_sum(cost), the smallest total of the cell costs along a right/down path, including both corners.

Challenge 2

Write int largest_square(const std::vector<std::string>& g): the side of the biggest square made only of # cells. Let s[r][c] be the side of the largest such square whose bottom-right corner is (r, c): for a # cell it's 1 plus the smallest of the values above, to the left and diagonally up-left.

Challenge 3

Write int min_falling_path(const std::vector<std::vector<int>>& g): start on any cell of the top row and move down one row at a time, to the cell directly below or diagonally below-left or below-right. Return the smallest possible total of the cells visited. Keep just one row of best totals.

Previous: Bottom-up tables and coin change Next: Longest common subsequence