Grids and 2-D DP

When a state needs two numbers, the table becomes a grid. The input is often a grid too, such as a map or a board, and then the table has the same shape as the input. This lesson fills such tables, and shows what to do when no safe order exists.

Two numbers per state

A state (r, c) is a cell: row r, column c. The rule says how a cell’s answer comes from other cells. If every cell reads only cells above it or to its left, filling row by row, left to right, is a safe order (lesson 3). The cost is the number of cells times the work per cell, usually O(rows × cols).

States with two numbers also appear without any grid in the input: a position in each of two strings (lesson 7), or an item and a weight (lesson 8). The same picture, and the same order, work for those.

The cheapest path

Each cell of a grid has a cost. A route starts at the top-left cell, moves only right or down, and ends at the bottom-right cell. Its cost is the sum of the costs of the cells it visits. Find the cheapest route.

Let cheap[r][c] be the cheapest cost of a route from the start to cell (r, c). The last move into (r, c) came from above or from the left. Whichever it was, the route up to that cell must itself be the cheapest to that cell; otherwise swapping in a cheaper one would make a cheaper route to (r, c). So:

cheap[r][c] = cost[r][c] + min(cheap[r - 1][c],
                                cheap[r][c - 1])

Cells on the top row have no cell above; cells in the left column have no cell to the left. Step through the first version of the figure. Each arrow points to the neighbour the value came from.

def cheapest_path(cost):
    rows, cols = len(cost), len(cost[0])
    INF = float("inf")
    above = [INF] * cols           # a row above the grid
    for r in range(rows):
        row = [0] * cols
        for c in range(cols):
            left = row[c - 1] if c > 0 else INF
            best = min(above[c], left)
            if r == 0 and c == 0:
                best = 0               # the start
            row[c] = cost[r][c] + best
        above = row
    return above[-1]

The row of infinities above the grid stands for cells that cannot be reached, so the top row needs no separate case. Two rows are kept: O(rows × cols) time, O(cols) space.

Counting paths

To count routes instead of finding the cheapest, add instead of taking the smallest: the routes into (r, c) are the routes into the cell above plus the routes into the cell to the left. The two groups do not overlap, because their last moves differ. A blocked cell has no routes through it, so its count is 0. The second version of the figure fills this table.

Without blocked cells, the count for an r × c grid has a formula: a route is a list of r − 1 down moves and c − 1 right moves in some order, and the number of such orders is math.comb(r + c - 2, r - 1). For 4 rows and 5 columns that is 35 (MATH-6 explains comb). Blocked cells break the formula, but not the table.

When the order is not obvious

• Moves up and right (from the bottom-left corner): cells read the cell below and the cell to the left, so fill from the bottom row upwards. The safe order follows the moves.
• Moves in all four directions: a cell can depend on a cell that depends on it, so there is no safe order at all. The states form a graph with loops, not a DAG. The cheapest route is then a shortest-path problem, solved with Dijkstra’s method (PATH-3) rather than a table.
• The answer depends on what comes later. In some puzzles you walk through a grid and must never run out of health. The health you need at a cell depends on the cells after it, so the table is filled backwards, from the end to the start.

Other grid problems

• A triangle of numbers, each row one longer than the one above; move down to either of the two numbers below. Filling from the bottom row upwards leaves the answer at the top, with no special cases.
• Squares and rectangles of free cells. The largest free square ending at a cell depends on three neighbours (DYNP-P5). The largest free rectangle needs a different method: one row at a time, using the largest rectangle under a bar chart (STAQ-5).
• Two walkers at once, such as two people collecting coins on their way down the grid. The state must say where both are: three numbers (the step, and the two columns), because the two walkers are at the same step.

Now try DYNP-P5, The largest free square.