231. Unique Grid Paths

Why this mechanism works

Name both axes before filling the table: dp[r][c] counts paths ending at that cell. The final move comes from above or from the left, and these route classes are disjoint. Boundary cells have only one predecessor; the origin needs an explicit seed of one.

State and boundaries

dp[r][c] is the complete count for exactly cell (r,c). Row-major order completes its top and left predecessors before use.

Protocol

1. Handle zero dimensions.
2. Allocate a zero table and seed the origin with one.
3. Scan cells in row-major order, skipping the origin.
4. Add the top count if present and the left count if present.
5. Return the destination count.

Visualization

3x3 path-count table
1 1 1
1 2 3
1 3 6
each interior value = top + left

Python implementation

def unique_paths(rows, cols):
    if rows == 0 or cols == 0:
        return 0
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1
    for r in range(rows):
        for c in range(cols):
            if r == c == 0:
                continue
            dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
    return dp[-1][-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 unique_paths: if rows == 0 or cols == 0:
rows=3; cols=3

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=3; cols=3; _=0

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=3; cols=3; _=1

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=3; cols=3; _=2

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=3; cols=3; dp=[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

L5 unique_paths: dp[0][0] = 1
rows=3; cols=3; dp=[[1, 0, 0], [0, 0, 0], [0, 0, 0]]

L6 unique_paths: for r in range(rows):
rows=3; cols=3; dp=[[1, 0, 0], [0, 0, 0], [0, 0, 0]]; r=0

L7 unique_paths: for c in range(cols):
rows=3; cols=3; dp=[[1, 0, 0], [0, 0, 0], [0, 0, 0]]; r=0; c=0

... 14 intermediate state changes omitted ...

L7 unique_paths: for c in range(cols):
rows=3; cols=3; dp=[[1, 1, 1], [1, 2, 3], [1, 0, 0]]; r=2; c=1

L10 unique_paths: dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
rows=3; cols=3; dp=[[1, 1, 1], [1, 2, 3], [1, 3, 0]]; r=2; c=1

L7 unique_paths: for c in range(cols):
rows=3; cols=3; dp=[[1, 1, 1], [1, 2, 3], [1, 3, 0]]; r=2; c=2

L10 unique_paths: dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
rows=3; cols=3; dp=[[1, 1, 1], [1, 2, 3], [1, 3, 6]]; r=2; c=2

L2 unique_paths: if rows == 0 or cols == 0:
rows=1; cols=1

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=1; cols=1; _=0

L4 unique_paths: dp = [[0] * cols for _ in range(rows)]
rows=1; cols=1; dp=[[0]]

L5 unique_paths: dp[0][0] = 1
rows=1; cols=1; dp=[[1]]

L6 unique_paths: for r in range(rows):
rows=1; cols=1; dp=[[1]]; r=0

L7 unique_paths: for c in range(cols):
rows=1; cols=1; dp=[[1]]; r=0; c=0

Why the solution is correct

The origin's empty path is the base. Every path into another cell ends with exactly one of the two permitted moves. Removing that move maps it uniquely to a path counted by the corresponding predecessor. Summing their complete counts therefore counts every route once.

Time and space

O(rows*cols) additions and table entries. Exact counts can require many bits; the table is pedagogically explicit rather than space-compressed.

Common mistakes

Seeding every cell with one and also adding predecessors overcounts. A zero-sized grid has no origin to seed.

Reasoning card

Transfer exercise

Compress the table to one row, explaining which old and new row values each update reads.