Skip to main content
2D DP

Unique Paths / Grid DP

Count paths from top-left to bottom-right, moving only right or down. dp[i][j] = dp[i−1][j] + dp[i][j−1] — you arrive from above or from the left. Extend to obstacles, minimum cost paths, etc.

O(m*n)
·
O(m*n)

How It Works

Grid DP counts or optimizes paths through a matrix when movement is restricted, typically to right and down. Because you can only enter cell (i, j) from above or from the left, dp[i][j] = dp[i-1][j] + dp[i][j-1] for counting paths, or min/max of those neighbors plus the cell cost for path optimization. The first row and column form the base cases since they have only one way in.

Filling the table row by row visits each of the m×n cells once, giving O(mn) time versus the combinatorial explosion of enumerating paths (there are C(m+n-2, m-1) of them). Since each row depends only on the previous row, space compresses to O(n). Obstacles simply zero out a cell; costs change addition to min-plus.

Step-by-Step Visualization

Count unique paths in 3x3 grid (right or down)
1
0
1
1
1
2
1
3
2
4
3
5
1
6
3
7
6
8
Start(0,0)
End(2,2)
1/3

Code

Java
static int uniquePaths(int m, int n) {
  int[][] dp = new int[m][n];
  for (int[] row : dp) Arrays.fill(row, 1);

  for (int i = 1; i < m; i++)
    for (int j = 1; j < n; j++)
      dp[i][j] = dp[i-1][j] + dp[i][j-1];

  return dp[m-1][n-1];
}
// uniquePaths(3, 3) → 6

Tips & Gotchas

1dp[i][j] = number of paths to reach (i,j)
2Can only come from top or left: dp[i][j] = dp[i-1][j] + dp[i][j-1]
3First row and first column are all 1s

Practice Problems

  • 1Unique Paths
  • 2Unique Paths II
  • 3Minimum Path Sum
  • 4Maximal Square
  • 5Dungeon Game

About the 2D DP Pattern

The state needs two variables — typically two indices (comparing two sequences), or a position in a grid. dp[i][j] depends on dp[i−1][j], dp[i][j−1], or dp[i−1][j−1]. Fills a 2D table.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

  • Climbing Stairs
  • Coin Change
  • Longest Common Subsequence
  • 0/1 Knapsack
  • Edit Distance
  • House Robber
  • Longest Increasing Subsequence
  • Word Break

Frequently Asked Questions

When do I count paths versus minimize a path sum?

Read the objective: 'how many ways' means summing dp[i-1][j] + dp[i][j-1], while 'cheapest path' means taking min of the two entries plus the current cell's cost. The table shape and fill order are identical; only the combining operation changes.

Why does Dungeon Game fill the table backward?

The health you need at a cell depends on what lies ahead, not behind — you must survive the rest of the path. Defining dp[i][j] as the minimum health needed upon entering (i, j) and filling from the bottom-right makes the recurrence well-defined.

Can grid DP handle movement in all four directions?

Not directly, because dp[i][j] would depend on cells that depend back on it, creating cycles. Four-directional movement turns the problem into a shortest-path question, which calls for BFS or Dijkstra instead of a single-pass table fill.