A grid becomes DP when the dependencies stop cycling

Picture

On a board where you may move only right or down, every move makes irreversible progress. To count routes to the exit, a square asks its right and lower neighbors for their route counts. The board is a graph, and the movement restriction makes its dependency graph acyclic.

Predict

On a clear 2×3 board, moving from the top-left square to the bottom-right, how many routes exist? Count moves, not visited squares.

Reveal the reasoning

Three: RRD, RDR, and DRR. There must be two right moves and one down move. Different prefixes that reach the same square can reuse the count of remaining continuations.

Go deeper: state coordinates describe where the question starts

Let paths(r,c) count ways to finish from (r,c) on a fixed rectangular board. Zero is open and one is blocked. Out-of-bounds or blocked squares contribute zero; an open destination contributes one empty continuation.

from functools import cache

def count_routes(board):
    if not board or not board[0]:
        return 0
    rows, cols = len(board), len(board[0])
    @cache
    def paths(r, c):
        if r >= rows or c >= cols or board[r][c] == 1:
            return 0
        if (r, c) == (rows - 1, cols - 1):
            return 1
        return paths(r + 1, c) + paths(r, c + 1)
    return paths(0, 0)

assert count_routes([[0, 0, 0], [0, 0, 0]]) == 3
assert count_routes([[0, 1], [0, 0]]) == 1
assert count_routes([[1]]) == 0
assert count_routes([[0]]) == 1

There are O(RC) states, two transitions each, and O(RC) cached storage. The stack depth is O(R+C). A tabulation of this suffix recurrence fills from bottom-right toward top-left because dependencies lie rightward and downward.

Two coordinates are needed here because rows and columns jointly determine location. But physical input dimensions do not dictate DP dimensions: a one-dimensional item list can need (index, capacity), and a two-dimensional board with resources can need three coordinates.

Analogy limit: a board does not automatically imply DP. Movement and revisit rules determine whether this recurrence works.

Change one rule

Allow up and left moves too, with unlimited revisits. Can the same recurrence simply add two more neighbors?

Check the variation

No. Dependencies now cycle, recursive caching cannot resolve them this way, and some instances have infinitely many walks to the destination. “Shortest route,” “simple routes,” and “routes using exactly t moves” are different finite questions with different states or algorithms.

Connect

3D budget DP changes one rule on this board. Compression reuses rows of stored answers. String DP creates a two-dimensional state space without a physical board.