Grid DP

Problem

You are given a rectangle of cells. You may be asked how many ways there are to walk from the top-left to the bottom-right moving only right or down, the cheapest such walk, the largest block of ones, or the longest chain of growing values. Trying every walk is exponential: a grid with r rows and c columns has C(r + c - 2, r - 1) right/down routes. But the routes into a cell all pass through one of only two cells just before it, so the answer for a cell can be built from the answers for those two.

Intuition

Picture a spreadsheet where each cell is a formula pointing at the cell above and the cell to its left. If you fill it row by row, every formula finds its inputs already computed. That is all a grid DP is: choose what a cell means, write the formula in terms of earlier cells, and read the answer from the last cell.

The only real work is choosing the meaning. For counting it is "how many ways reach this cell". For cheapest routes it is "the least total cost of any route that ends here". For squares it is "the biggest all-ones square whose bottom-right corner is this cell"; pinning down the corner is what makes the formula work.

When moves go in all four directions, there is no row-by-row order that works. The fix is to let recursion find the order: ask a cell for its answer, and let it ask its neighbours. If the rule forbids cycles, as "strictly increasing" does, a cache makes every cell computed once.

Each open cell is the sum of the cell above and the cell to the left; the blocked cell is a zero that feeds nothing. The blue cell is the answer. The diagram scrolls sideways on a narrow screen.

Mechanics

Counting routes

Let ways[r][c] be the number of right/down routes from the start to cell (r, c). The first row and first column have one route each, since there is only one way to stay on an edge. Elsewhere, ways[r][c] = ways[r - 1][c] + ways[r][c - 1]. A blocked cell is set to 0 before anything uses it. Because a row depends only on the row above, one list of length c is enough: overwrite it in place, adding the left neighbour as you go.

Cheapest route

Let cost[r][c] be the least total of cell values along any route ending at (r, c). Then cost[r][c] = grid[r][c] + min(cost[r - 1][c], cost[r][c - 1]), using only the neighbours that exist on an edge. The recurrence is correct because a cheapest route to (r, c) must arrive from above or from the left, and its earlier part has to be a cheapest route to that neighbour: otherwise swapping in a cheaper one would improve it. To recover the route itself, walk back from the corner, each time stepping to whichever neighbour has the smaller cost.

Blue cells lie on a cheapest route, recovered by walking back from the bottom-right cell to the cheaper neighbour each time.

Largest square of ones

Let side[r][c] be the side of the largest all-ones square whose bottom-right corner is (r, c). It is 0 if the cell is 0, 1 on the top row or left column, and otherwise 1 + min(side[r - 1][c], side[r][c - 1], side[r - 1][c - 1]). Why the minimum? A square of side k at (r, c) needs squares of side at least k - 1 ending directly above, directly left and diagonally up-left, since those are its three sub-squares that overlap it. Conversely, if all three neighbours support side k - 1 and the cell itself is 1, the union of those squares plus the cell is a solid square of side k. The area is the best side squared.

Four-direction moves: memoized DFS

Let length[r][c] be the longest strictly increasing path that starts at (r, c). It is 1 plus the best length over neighbours holding a bigger value, or just 1 if none is bigger. Row-by-row order does not work here, since a cell depends on neighbours in every direction. Recursion with a cache does: the strict increase means each recursive call moves to a larger value, so the calls can never loop back, and every cell is solved exactly once. This is the grid-graph DFS from the grid graphs page with a memo table added.

Blue cells form one longest path, found by following from the best start to a neighbour whose length is exactly one less.

Worked example

Routes with an obstacle. On a 3 by 4 grid with the middle cell (row 1, column 1) blocked, the table is 1, 1, 1, 1, 1, 0, 1, 2, 1, 1, 2, 4, so there are 4 routes. Check one cell by hand: the cell at row 1, column 3 has 1 from above and 1 from the left, giving 2.

Cheapest route. For the grid 1, 3, 1, 4, 1, 5, 1, 2, 4, 2, 1, 3 the cost table is 1, 4, 5, 9, 2, 7, 6, 8, 6, 8, 7, 10, so the cheapest route costs 10. One such route visits (0, 0) then (0, 1) then (0, 2) then (1, 2) then (2, 2) then (2, 3).

Largest square. The ones-and-zeros grid gives side table 1, 0, 1, 1, 1, 1, 1, 1, 2, 2, 0, 1, 2, 2, 0, 1, 1, 2, 3, 0. The largest side is 3, so the area is 9, with its bottom-right corner at (3, 3). That corner cell took 1 plus the smallest of its three neighbours, which are 2, 2 and 2.

Longest increasing path. For the value grid the memoized DFS fills 5, 4, 3, 2, 5, 2, 1, 2, 1, and the answer is 5.

Implementation

def unique_paths(rows, cols):
    ways = [1] * cols
    for _ in range(1, rows):
        for c in range(1, cols):
            ways[c] += ways[c - 1]      # above is the old ways[c]
    return ways[-1]


def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    cost = [0] * cols
    for r in range(rows):
        for c in range(cols):
            best = min(
                cost[c] if r else float("inf"),
                cost[c - 1] if c else float("inf"),
            )
            cost[c] = grid[r][c] + (0 if best == float("inf") else best)
    return cost[-1]

from functools import cache


def longest_increasing_path(matrix):
    rows, cols = len(matrix), len(matrix[0])

    @cache
    def start_at(r, c):
        best = 1
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                best = max(best, 1 + start_at(nr, nc))
        return best

    return max(start_at(r, c) for r in range(rows) for c in range(cols))

Variations and edge cases

def unique_paths_with_obstacles(grid):
    if grid[0][0] or grid[-1][-1]:
        return 0
    cols = len(grid[0])
    ways = [0] * cols
    ways[0] = 1
    for row in grid:
        for c in range(cols):
            if row[c]:
                ways[c] = 0
            elif c:
                ways[c] += ways[c - 1]
    return ways[-1]


def maximal_square(matrix):
    cols = len(matrix[0])
    side = [0] * (cols + 1)             # one padding column on the left
    best = 0
    for row in matrix:
        diagonal = 0                    # side up-left of the current cell
        for c in range(1, cols + 1):
            above = side[c]
            side[c] = 1 + min(side[c], side[c - 1], diagonal) if row[c - 1] == "1" else 0
            diagonal = above
            best = max(best, side[c])
    return best * best

• Blocked start or end. If either corner is blocked the answer is 0 before any table work.
• Edges. Row 0 and column 0 have only one predecessor. Handle them with padding or an explicit if, never by indexing -1, which silently wraps in Python.
• One-row or one-column grid. The answer is 1 way, or the sum of the cells, which the same code gives without a special case.
• Rolling the row. When shrinking to one list, the diagonal value is overwritten before you read it unless you save it first, as diagonal does above.
• Characters versus numbers. Some inputs give cells as strings like "1"; compare against the right type.
• Memo DFS depth. A long spiral can recurse up to rows times cols deep. Python's default limit is about 1000, so very large grids need the limit raised or an iterative order by sorting cells by value.

Complexity and tradeoffs

• Time: O(r · c) for every pattern here; each cell does a constant amount of work. The memoized DFS visits each cell once and looks at 4 neighbours.
• Space: O(r · c) for a full table, O(c) when only the previous row is needed. The memo DFS needs the full table, plus recursion depth.
• Baseline. Enumerating routes is exponential; for a 15 by 15 grid the count is already over 40 million.
• Count by formula. For plain Unique Paths with no obstacles the answer is the binomial C(r + c - 2, r - 1), computed in O(min(r, c)); the table is for when the grid has obstacles or costs.
• When it fails. If moves can go up or left too, row order no longer works: use Dijkstra on the grid when costs are non-negative, or Bellman-Ford if they can be negative. If a path may revisit cells, there is no DP order at all.

Problems

Unique Paths is the entry point, and the same table with a different formula answers Minimum Path Sum and Maximal Square. Longest Increasing Path is the hard one: it is the same idea carried to four-direction moves, with recursion supplying the order.

Medium

• 62. Unique Paths Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The paths into a cell are the paths into the cell above plus the cell to its left, and one row of memory is enough.
• 63. Unique Paths II NeetCode 250
  Use the same path-count recurrence, but any obstacle cell contributes zero paths.
• 64. Minimum Path Sum NeetCode 250
  Each cell's cheapest cost is its own value plus the cheaper of the cell above and the cell to the left.
• 221. Maximal Square Grind 169
  The largest square ending at a cell is one more than the smallest of the squares ending above, to the left and diagonally.

Hard

• 329. Longest Increasing Path in a Matrix Grind 169 NeetCode 150 NeetCode 250
  Memoize the longest increasing path starting at each cell; the strictly increasing rule rules out cycles, so DFS with a cache is safe.

Connections

Every grid DP is a shortest-path or counting problem on a directed acyclic graph whose nodes are cells, which links it to the DP fundamentals page and to topological ordering. The memoized DFS is the same traversal as flood fill with a cache bolted on.

Check yourself

References

• Bellman, R., Dynamic Programming, Princeton University Press, 1957.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14 on dynamic programming.
• Skiena, S., The Algorithm Design Manual, chapter 10 on dynamic programming.
• Sedgewick and Wayne, Algorithms, section 4.4 (acyclic shortest and longest paths): a grid DP is a path problem on a DAG whose cells, read row by row, are already in topological order.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.