Dynamic Programming on Grids Pattern

When to use Dynamic Programming on Grids

• The problem operates on a 2D matrix or implicit grid and asks for a count, min/max cost, or longest path from one corner to another.
• Moves are restricted to a small fixed set of directions (right/down, or all four neighbors) so each cell has O(1) predecessors.
• The answer at cell (i, j) is expressible as a recurrence on (i-1, j), (i, j-1), or adjacent cells with no cycles.
• Memoization on a (row, col) state collapses the recursive search to O(m * n) unique subproblems.
• You need the actual minimum-cost or maximum-value path, not just whether one exists.

Template

function gridDP(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const fromTop = i > 0 ? dp[i - 1][j] : Infinity;
      const fromLeft = j > 0 ? dp[i][j - 1] : Infinity;
      dp[i][j] = grid[i][j] + Math.min(fromTop, fromLeft);
    }
  }
  return dp[m - 1][n - 1];
}

Common mistakes

• Iterating the grid in the wrong order — forgetting to fill row 0 and column 0 as base cases before the main double loop.
• On Dungeon Game, applying the recurrence left-to-right instead of right-to-left, which misses the constraint that health must stay positive at every step.
• On Maximal Square, storing the side length but reporting it directly as the area instead of squaring it.
• Allocating an O(m * n) table when a rolling 1D array of size O(n) suffices, then running out of memory on large inputs.
• Treating an obstacle cell as a valid transition source in Unique Paths II, double-counting paths that should be blocked.