Grid dynamic programming

Overview

Grid DP computes an answer for every cell of a matrix from its neighbors, usually the cell above and the cell to the left when movement is restricted to right and down. dp[r][c] might be the number of paths to the cell, the minimum cost to reach it, or the size of the largest square ending there.

Because each row depends only on the previous row, grid DP almost always compresses to a single 1D array of length cols. More advanced variants add a third dimension, such as two walkers moving together (Cherry Pickup) or remaining steps.

When to use it

• Movement is restricted (right / down, or down with diagonals).
• Count paths, minimize path cost, or maximize collected value.
• Largest square or rectangle of 1s ending at each cell.
• Obstacles block some cells.

Problem patterns it solves

Where it is used in real software

Key terms

dp[r][c]

Answer for paths ending at cell (r, c).

First row / column

Base cases: reachable only in one direction.

Obstacle

A blocked cell whose dp value is 0 (paths) or Infinity (cost).

Rolling row

dp[c] holds the current row; dp[c - 1] is the left cell and old dp[c] is the cell above.

How it works, step by step

1. 1
   Define the cell meaning

   dp[r][c] = number of paths from (0, 0) to (r, c).

2. 2
   Base cases

   dp[0][0] = 1; the first row and column each have one path unless blocked.

3. 3
   Transition

   dp[r][c] = dp[r - 1][c] + dp[r][c - 1] (or min / max for costs).

4. 4
   Handle obstacles

   If the cell is blocked, dp[r][c] = 0.

5. 5
   Compress

   dp[c] += dp[c - 1] row by row gives O(cols) space.

Minimum path sum

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]; dp shows minimum cost to reach each cell

Minimum cost 7 via 1 -> 3 -> 1 -> 1 -> 1. Each cell took the cheaper of arriving from above or from the left.

Implementation

1function uniquePathsWithObstacles(grid) {2  const cols = grid[0].length;3  const dp = new Array(cols).fill(0);4  dp[0] = 1;5  for (const row of grid) {6    for (let c = 0; c < cols; c++) {7      if (row[c] === 1) dp[c] = 0;          // obstacle8      else if (c > 0) dp[c] += dp[c - 1];   // above (old dp[c]) + left9    }10  }11  return dp[cols - 1];12}13 14function minPathSum(grid) {15  const rows = grid.length, cols = grid[0].length;16  const dp = new Array(cols).fill(Infinity);17  dp[0] = 0;18  for (let r = 0; r < rows; r++) {19    for (let c = 0; c < cols; c++) {20      const left = c > 0 ? dp[c - 1] : Infinity;21      dp[c] = grid[r][c] + Math.min(dp[c], left);22    }23  }24  return dp[cols - 1];25}26 27function maximalSquare(matrix) {28  const rows = matrix.length, cols = matrix[0].length;29  const dp = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));30  let best = 0;31  for (let r = 1; r <= rows; r++) {32    for (let c = 1; c <= cols; c++) {33      if (matrix[r - 1][c - 1] === "1") {34        dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);35        best = Math.max(best, dp[r][c]);36      }37    }38  }39  return best * best;40}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Initializing the whole first row to 1 when an obstacle exists.

  Fix: Cells after an obstacle in the first row are unreachable (0).

• Forward-filling when the constraint depends on the future.

  Fix: Dungeon Game must be filled from the goal backward.

• Recursion without memoization on grids.

  Fix: Plain recursion is exponential; cache each cell.

Interview questions

Practice problems