Two-Dimensional DP

How to think about it

dp[i][j] = answer for a subproblem on prefix i and j (or cell (i,j)). Fill by increasing i+j or scanning rows. Often the answer sits at dp[m][n] or dp[m-1][n-1].

Template shapes

Shape	Core move	Notes
Grid paths	from top/left	Obstacles zero out
String DP	match → diag+1	else min/max of skips
Rolling array	Keep prev row only	Save space

Complexity baseline

O(m·n) time and space (or O(min(m,n)) space with rolling).

From template to problem

1. Define dp[i][j] in words.
2. Initialize first row/col.
3. Transition from the geometric neighbors of the recurrence.
4. Return the corner cell.

/** 2D DP template: unique paths (right/down only). dp[c] rolled per row. */
export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}

/** 2D DP template: unique paths (right/down only). dp[c] rolled per row. */
export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}