DPAlgorithmaka matrix DP, lattice path DP, path counting

Grid DP

State is a cell (r, c); the answer for a cell comes from its allowed predecessor cells (usually up and left).

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

Grid DP applies when moves through a matrix are monotone — typically only right and down — so the cells form a DAG in row-major order. dp[r][c] is the best/count for reaching (r, c) and depends only on dp[r-1][c] and dp[r][c-1] (plus dp[r-1][c-1] for problems like maximal square). Unique Paths, Minimum Path Sum, Unique Paths with Obstacles, Maximal Square, Dungeon Game (which runs from the bottom-right backwards), Cherry Pickup, and triangle minimum path all fit.

Time and space are O(rows × cols); space drops to O(cols) with a rolling row. Constraints of rows, cols ≤ 1000 or a total of ≤ 10^6 cells are typical.

If moves are allowed in all four directions, the grid is no longer a DAG and DP does not apply directly — use Breadth-First Search (BFS) / Dijkstra's Algorithm for shortest paths, or memoized DFS with a strictly increasing value condition (longest increasing path in a matrix) which restores acyclicity.

gridmatrixpathsO(rc)monotone moves

Intuition

A mental model before the formal terms.

Imagine water flowing only down and right from the top-left corner. Each cell collects "how many ways could water reach me" as the sum of what flows from above and from the left. Fill the first row and column with 1s (only one way to walk straight), then every other cell is the sum of its two upstream neighbours — Pascal's triangle drawn on a rectangle.

For minimum path sum, swap "sum of ways" for "cheapest of the two upstream costs, plus my own cost".

How it works

  1. State: dp[r][c] = answer for paths from the start to (r, c) (or from (r, c) to the end for suffix-style DPs like Dungeon Game).
  2. Transition: combine over allowed predecessors — dp[r-1][c] and dp[r][c-1] — with the cell's own contribution (+ grid[r][c] for costs, nothing for counts). Obstacles set dp[r][c] = 0 / INF.
  3. Base cases: the start cell, and the first row/column which have a single predecessor. Using a padded table with a virtual row/column of INF (min) or 0 (count) avoids special-casing.
  4. Order: row-major (or reverse row-major for suffix DPs). Table: 2D. Optimization: one row updated left to right — dp[c] still holds the "above" value when read and dp[c-1] is already the "left" value.

Why it works

Monotone moves mean every path to (r, c) enters from exactly one of the allowed predecessor cells, and the portion before that is itself a path to that predecessor. Optimal substructure and exhaustive enumeration of the last step give correctness.

Row-major order is a topological order because predecessors always have a smaller row or the same row and smaller column.

Recognition

How to tell a problem wants this.

  • A 2D grid where you may only move right/down (or the problem's moves are otherwise acyclic).
  • Asks for the number of paths, minimum/maximum path cost, or the largest square/rectangle satisfying a property.
  • A triangle or staircase-shaped input where each row depends on the one above.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

1→1
3
1
2
1
5
1
3
4
2
1
1
dp (min sum to reach cell)
0123
1
1/13Each cell shows "value→dp". Moving only right or down, the cheapest way to reach the start is its own value, 1.
Cell being filledDependency (up / left)ComputedOptimal path
PseudocodeLearn Grid DP →
1dp[0][0] = g[0][0]
2for each cell (r, c) in row-major order:
3  up = dp[r-1][c] if r > 0 else ∞
4  left = dp[r][c-1] if c > 0 else ∞
5  dp[r][c] = g[r][c] + min(up, left)
6return dp[R-1][C-1]; trace back to reconstruct path
Variables
R3
C4
Complexity
worst O(rows × cols)
space O(rows × cols), reducible to O(cols)
Speed

Pseudocode

1# minimum path sum, moves right/down only
2dp = rows x cols
3dp[0][0] = grid[0][0]
4for r in 0..rows-1:
5  for c in 0..cols-1:
6    if r == 0 and c == 0: continue
7    up   = dp[r-1][c] if r > 0 else INF
8    left = dp[r][c-1] if c > 0 else INF
9    dp[r][c] = grid[r][c] + min(up, left)
10return dp[rows-1][cols-1]

Implementations

1# Representative problem: minimum path sum in a grid (moves: right, down)
2def min_path_sum(grid: list[list[int]]) -> int:
3    n, m = len(grid), len(grid[0])
41 · Table sized like the grid
5    dp = [[0] * m for _ in range(n)]    # dp[r][c] = cheapest way to reach (r, c)
62 · Base cases: first row and first column
7    dp[0][0] = grid[0][0]
8    for c in range(1, m):               # only reachable from the left
9        dp[0][c] = dp[0][c - 1] + grid[0][c]
10    for r in range(1, n):               # only reachable from above
11        dp[r][0] = dp[r - 1][0] + grid[r][0]
123 · Fill row-major
13    for r in range(1, n):
14        for c in range(1, m):
154 · Transition: arrive from above or from the left
16            dp[r][c] = grid[r][c] + min(dp[r - 1][c], dp[r][c - 1])
175 · Read the answer
18    return dp[n - 1][m - 1]
19 
20 
21if __name__ == "__main__":
22    print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))  # 7 (1-3-1-1-1)
Walkthrough
  1. Representative example of grid DP: dp[r][c] is the cheapest path to (r, c); only the top and left neighbours feed it.
  2. The table is built with a comprehension so each row is a distinct list.
  3. First row and column are running sums — each has one predecessor.
  4. The double loop fills row-major; both dependencies are final when read.
  5. The bottom-right cell is the answer (7 for the sample grid).
Complexity (this implementation)
time O(n·m) · space O(n·m), reducible to O(m) with one rolling row
Language notes
  • The rolling-row form is idiomatic: keep one list row, update in place left to right.
  • Mutating the input grid in place (grid[r][c] += min(...)) gives O(1) extra space but destroys the caller's data — say so if you do it.
  • For heavy numeric grids numpy row operations can vectorize the recurrence per row, though the left-neighbour dependency limits full vectorization.
Common mistakes in this language
  • [[0] * m] * n — aliased rows.
  • Forgetting that the first row/column need their own seeding loop.
  • Mixing up n (rows) and m (columns) on non-square grids — test with a rectangular input.
Language differences that matter here
  • Row aliasing when building the table: Python list multiplication and JS/TS fill(row) share one row object; C++ nested vectors copy by value.
  • Path-counting variants overflow C++ int/long long and lose precision in JS/TS past 2^53; Python ints are exact.
  • Flat typed storage (Int32Array, flat std::vector) is the standard speedup in JS/TS and C++; pure-Python gains more from the rolling row than from flattening.

Complexity

Best
—
Average
—
Worst
O(rows × cols)
Space
O(rows × cols), reducible to O(cols)

Each cell does O(1) work with a constant number of predecessors.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Monotone movement on a grid (right/down, or any acyclic move set).
  • Counting lattice paths, minimum/maximum path cost, largest square/rectangle of 1s.
  • Triangle / staircase inputs where each row depends on the previous.
Avoid it when
  • Movement in all four directions with no monotone value — cycles exist; use Breadth-First Search (BFS) (unweighted) or Dijkstra's Algorithm (weighted).
  • You need the actual shortest path with obstacles in an unweighted grid — BFS is simpler and equally fast.
  • The grid is huge (10^4 × 10^4) and only a few cells matter — think sparse or coordinate-compress.

Alternatives

Breadth-First Search (BFS)Dijkstra's Algorithm2D Prefix Sum2D (Two-Sequence) DP

Common mistakes

  • Treating the first row/column like interior cells and reading out of bounds; pad the table or special-case them.
  • Obstacle cells: setting their count to 1 (leaked from the base row) instead of 0.
  • For Dungeon Game-style "minimum initial health", running the DP forward instead of backward from the goal.
  • Rolling row updated right-to-left, which destroys the "above" value before it is read — go left-to-right for up/left transitions.

Interview patterns

  • Unique Paths I/II, Minimum Path Sum, Triangle.
  • Maximal Square (dp[r][c] = 1 + min(up, left, diag)), Count Square Submatrices.
  • Dungeon Game (backwards DP), Cherry Pickup (two walkers, 3D state).
  • Longest Increasing Path in a Matrix (memoized DFS; the increasing condition makes it a DAG).
Interview questions on this
Mock interviews

Example problems

Range Sum Query 2D — ImmutablemediumShortest Path in Binary MatrixmediumUnique Pathsmedium