DP on Grids

Grid DP is 2D dynamic programming where the state is the current cell position (row, col). Movement is typically restricted (right and down only, or all four directions), which defines the dependency order for filling the table.

The core pattern: dp[r][c] = best value achievable at cell (r, c), computed from neighboring cells that were already solved.

Unique Paths — Count Routes

A robot moves in an m×n grid from top-left to bottom-right. It can only move right or down. How many distinct paths exist?

State: dp[r][c] = number of paths to reach cell (r, c) Recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1] (came from above or from left) Base cases: dp[0][c] = 1 and dp[r][0] = 1 (only one way to travel along edges)

// Unique Paths — O(m·n) time, O(m·n) space
function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
    }
  }

  return dp[m - 1][n - 1];
}

// Space optimization: O(n) space (rolling one row)
function uniquePathsOptimized(m, n) {
  let row = new Array(n).fill(1);

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      row[c] += row[c - 1];  // row[c] was dp[r-1][c], row[c-1] is dp[r][c-1]
    }
  }

  return row[n - 1];
}

// Unique Paths II — with obstacles
function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  if (grid[0][0] === 1) return 0;  // start is blocked

  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = 1;

  // Fill first column
  for (let r = 1; r < m; r++) {
    dp[r][0] = grid[r][0] === 1 ? 0 : dp[r - 1][0];
  }
  // Fill first row
  for (let c = 1; c < n; c++) {
    dp[0][c] = grid[0][c] === 1 ? 0 : dp[0][c - 1];
  }

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[r][c] = grid[r][c] === 1 ? 0 : dp[r - 1][c] + dp[r][c - 1];
    }
  }

  return dp[m - 1][n - 1];
}

console.log(uniquePaths(3, 7));                               // 28
console.log(uniquePathsWithObstacles([[0,0,0],[0,1,0],[0,0,0]])); // 2

Minimum Path Sum

Find the path from top-left to bottom-right (moving only right or down) with the minimum sum of values along the path.

State: dp[r][c] = minimum sum to reach (r, c) Recurrence: dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])

// Minimum Path Sum — O(m·n) time, O(1) extra space (modify in place)
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;

  // Fill first row
  for (let c = 1; c < n; c++) {
    grid[0][c] += grid[0][c - 1];
  }
  // Fill first column
  for (let r = 1; r < m; r++) {
    grid[r][0] += grid[r - 1][0];
  }

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
    }
  }

  return grid[m - 1][n - 1];
}

const grid = [[1,3,1],[1,5,1],[4,2,1]];
console.log(minPathSum(grid)); // 7  (1→3→1→1→1)

Warning

Modifying the input grid in-place saves O(m·n) space but mutates the input. In production, clone the grid first with `JSON.parse(JSON.stringify(grid))` or create a separate dp array.

Dungeon Game — Reverse DP

A knight starts at top-left and must reach bottom-right. Each cell has a value (positive = health gain, negative = health loss). The knight dies if health drops to 0 or below at any point. Find the minimum initial health needed.

Key insight: Forward DP fails here because minimum initial health at (0,0) depends on future cells. We must solve backward — from the bottom-right.

State: dp[r][c] = minimum health needed when entering cell (r, c) Recurrence:

Health needed after this cell: min(dp[r+1][c], dp[r][c+1])
Health needed before cell's effect: max(1, min_after - dungeon[r][c])
- If dungeon[r][c] is positive (heal), need less health going in
- Must always have at least 1 health

// Dungeon Game — O(m·n) time, O(m·n) space (reverse DP)
function calculateMinimumHP(dungeon) {
  const m = dungeon.length, n = dungeon[0].length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(Infinity));

  // Virtual border: dp[m-1][n] and dp[m][n-1] = 1 (knight needs 1 health at end)
  dp[m][n - 1] = 1;
  dp[m - 1][n] = 1;

  // Fill bottom-right to top-left
  for (let r = m - 1; r >= 0; r--) {
    for (let c = n - 1; c >= 0; c--) {
      const minAfter = Math.min(dp[r + 1][c], dp[r][c + 1]);
      dp[r][c] = Math.max(1, minAfter - dungeon[r][c]);
    }
  }

  return dp[0][0];
}

const dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]];
console.log(calculateMinimumHP(dungeon)); // 7

Tip

Dungeon Game is the classic example of why sometimes DP must go backward. Whenever the answer at a cell depends on future cells (not past cells), reverse the traversal direction.

Maximal Square

Find the largest square of 1s in a binary matrix and return its area.

State: dp[r][c] = side length of the largest square whose bottom-right corner is (r, c) Recurrence: If matrix[r][c] == '1': dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1

The minimum of the three neighbors limits the square size: if any neighbor has a smaller square, we can only extend up to that size.

// Maximal Square — O(m·n) time, O(m·n) space
function maximalSquare(matrix) {
  if (!matrix.length) return 0;
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  let maxSide = 0;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (matrix[r][c] === '0') continue;  // can't form a square ending here

      if (r === 0 || c === 0) {
        dp[r][c] = 1;  // border cells can only be 1x1 squares
      } else {
        dp[r][c] = Math.min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1;
      }

      maxSide = Math.max(maxSide, dp[r][c]);
    }
  }

  return maxSide * maxSide;  // area = side²
}

const matrix = [
  ['1','0','1','0','0'],
  ['1','0','1','1','1'],
  ['1','1','1','1','1'],
  ['1','0','0','1','0']
];
console.log(maximalSquare(matrix)); // 4 (2×2 square)

Cherry Pickup

Walk from top-left to bottom-right and back, collecting as many cherries as possible. Cells with -1 are thorns (blocked). A cherry disappears after being picked once.

Insight: Instead of two separate passes, model two people walking simultaneously from (0,0) to (n-1,n-1) at the same step count. At step t, person 1 is at (r1, c1) and person 2 at (r2, c2) where r1 + c1 = r2 + c2 = t.

State: dp[r1][r2][step] — but since step = r1+c1, c1 = step-r1 and c2 = step-r2. So state collapses to dp[r1][r2], iterating step from 0 to 2(n-1).

// Cherry Pickup — O(n³) time, O(n²) space
function cherryPickup(grid) {
  const n = grid.length;
  const NEG_INF = -Infinity;

  // dp[r1][r2] = max cherries when person1 is at row r1, person2 at row r2,
  //              both at the same step (c1 = step-r1, c2 = step-r2)
  let dp = Array.from({ length: n }, () => new Array(n).fill(NEG_INF));
  dp[0][0] = grid[0][0];

  for (let step = 1; step <= 2 * (n - 1); step++) {
    const next = Array.from({ length: n }, () => new Array(n).fill(NEG_INF));

    for (let r1 = Math.max(0, step - (n - 1)); r1 <= Math.min(n - 1, step); r1++) {
      const c1 = step - r1;
      if (grid[r1][c1] === -1) continue;

      for (let r2 = r1; r2 <= Math.min(n - 1, step); r2++) {
        const c2 = step - r2;
        if (grid[r2][c2] === -1) continue;

        // Cherries at current positions (avoid double-counting if same cell)
        let cherries = grid[r1][c1];
        if (r1 !== r2) cherries += grid[r2][c2];

        // Try all 4 previous step combinations (each person came from up or left)
        const best = Math.max(
          dp[r1][r2],         // both moved right
          dp[r1 - 1]?.[r2] ?? NEG_INF,    // p1 from up, p2 right
          dp[r1]?.[r2 - 1] ?? NEG_INF,    // p1 right, p2 from up
          dp[r1 - 1]?.[r2 - 1] ?? NEG_INF // both from up
        );

        if (best !== NEG_INF) {
          next[r1][r2] = Math.max(next[r1][r2], best + cherries);
        }
      }
    }
    dp = next;
  }

  return Math.max(0, dp[n - 1][n - 1]);
}

console.log(cherryPickup([[0,1,-1],[1,0,-1],[1,1,1]])); // 5

Path Reconstruction

To reconstruct the actual path in grid DP (not just the value), store parent pointers during the forward pass and backtrack from the answer.

// Minimum Path Sum with path reconstruction
function minPathSumWithPath(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  const from = Array.from({ length: m }, () => new Array(n).fill(null));

  dp[0][0] = grid[0][0];
  for (let c = 1; c < n; c++) { dp[0][c] = dp[0][c-1] + grid[0][c]; from[0][c] = 'left'; }
  for (let r = 1; r < m; r++) { dp[r][0] = dp[r-1][0] + grid[r][0]; from[r][0] = 'up'; }

  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      if (dp[r-1][c] < dp[r][c-1]) {
        dp[r][c] = grid[r][c] + dp[r-1][c];
        from[r][c] = 'up';
      } else {
        dp[r][c] = grid[r][c] + dp[r][c-1];
        from[r][c] = 'left';
      }
    }
  }

  // Backtrack
  const path = [];
  let r = m - 1, c = n - 1;
  while (r > 0 || c > 0) {
    path.push([r, c]);
    if (from[r][c] === 'up') r--;
    else c--;
  }
  path.push([0, 0]);
  return { cost: dp[m-1][n-1], path: path.reverse() };
}

const g = [[1,3,1],[1,5,1],[4,2,1]];
const { cost, path } = minPathSumWithPath(g);
console.log(cost);  // 7
console.log(path);  // [[0,0],[0,1],[0,2],[1,2],[2,2]]

Grid DP Pattern Summary

Problem	State	Recurrence	Direction
Unique Paths	Count paths to (r,c)	dp[r-1][c] + dp[r][c-1]	Top-left → bottom-right
Min Path Sum	Min cost to (r,c)	val + min(up, left)	Top-left → bottom-right
Dungeon Game	Min health at (r,c)	max(1, minAfter - val)	Bottom-right → top-left
Maximal Square	Square side at (r,c)	min(3 neighbors) + 1	Top-left → bottom-right
Cherry Pickup	Max cherries for 2 paths	Complex 4-way max	Left → right (by step)

When movement is right/down only, fill top-left to bottom-right
When answer depends on future cells (like Dungeon Game), fill in reverse
For counting paths, initialize borders to 1 (one way to reach them)
For optimization (min/max), initialize borders to accumulated values
Always handle grid boundary conditions before the main DP loop

Note

The grid DP pattern extends to graphs — just replace the 2D array with an adjacency list and DP over topological order. The state transitions follow edges instead of the four cardinal directions.