In the previous chapter, every DP state could be described with one number: a step, a house, or an amount.
But many problems need two numbers to describe where you are.
Imagine a robot standing in the top-left corner of a grid. To describe the robot's position, you need both a row and a column. One number is not enough.
That's where 2D Dynamic Programming comes in.
2D DP is dynamic programming where each state depends on two variables, so the answers are stored in a two-dimensional table dp[i][j].
The two variables can be:
A row and a column in a grid
An index in one string and an index in another string
An item number and a remaining capacity
In this chapter, we focus on grid problems, which are the easiest way to build intuition. The next two chapters use the same 2D idea for knapsack problems and string problems.
If you need a refresher on creating and looping over 2D arrays in Java, see the 2D Arrays chapter.
Problem 1: Unique Paths
A robot starts at the top-left cell of an m × n grid. It can only move right or down. How many different paths lead to the bottom-right cell?
For a 3 × 3 grid:
S . .
. . .
. . EThere are 6 paths. Two of them are:
Right → Right → Down → Down
Down → Right → Down → RightThink About the Last Move
Just like in 1D DP, ask how you arrived at cell (i, j). Since you can only move right or down, you came from:
(i-1, j)
↓
(i, j-1) → (i, j)Either from the cell above or the cell to the left. So:
paths to (i, j) = paths to (i-1, j) + paths to (i, j-1)The DP Formulation
State : dp[i][j] = number of paths from (0, 0) to (i, j)
Recurrence : dp[i][j] = dp[i-1][j] + dp[i][j-1]
Base cases : dp[0][j] = 1 (first row: only keep moving right)
dp[i][0] = 1 (first column: only keep moving down)
Order : row by row, left to right
Answer : dp[m-1][n-1]Filling the table for a 3 × 7 grid:
j=0 j=1 j=2 j=3 j=4 j=5 j=6
i=0 1 1 1 1 1 1 1
i=1 1 2 3 4 5 6 7
i=2 1 3 6 10 15 21 28 ← answerEach cell is just the cell above + the cell to the left. For example, dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10.
Because we fill row by row from left to right, the cell above and the cell to the left are always ready before we need them.
static long uniquePaths(int m, int n) {
long[][] dp = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}Complexity: There are m × n states and each takes O(1) work, so Time O(m × n) and Space O(m × n).
Fun fact: this particular problem also has a math formula. Every path has exactly m - 1 downs and n - 1 rights, so the answer is the number of ways to arrange them: C(m + n - 2, m - 1). For 3 × 7, that's C(8, 2) = 28. But the DP approach is what extends to harder versions, like the next one.
Problem 2: Unique Paths with Obstacles
Same robot, but now some cells are blocked (1 means blocked, 0 means free).
0 0 0
0 1 0
0 0 0The middle cell is blocked. How many paths remain?
One Small Change
A blocked cell can't be part of any path, so the number of ways to reach it is 0:
If grid[i][j] is blocked → dp[i][j] = 0
Otherwise → dp[i][j] = dp[i-1][j] + dp[i][j-1]This automatically handles the first row and column too. If a cell in the first row is blocked, every cell to its right becomes unreachable, because the only way to reach them was through the blocked cell.
Table:
grid dp
0 0 0 1 1 1
0 1 0 1 0 1
0 0 0 1 1 2 ← answerstatic int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dp[i][j] = 0;
} else if (i == 0 && j == 0) {
dp[i][j] = 1;
} else {
int fromTop = (i > 0) ? dp[i - 1][j] : 0;
int fromLeft = (j > 0) ? dp[i][j - 1] : 0;
dp[i][j] = fromTop + fromLeft;
}
}
}
return dp[m - 1][n - 1];
}Note that if the start cell itself is blocked, the first branch sets dp[0][0] = 0, and the answer is correctly 0.
Problem 3: Minimum Path Sum
Now each cell has a cost. Moving only right or down, find the path from top-left to bottom-right with the smallest total cost (including the start and end cells).
1 3 1
1 5 1
4 2 1The best path is:
1 → 3 → 1
↓
1
↓
1
Total = 1 + 3 + 1 + 1 + 1 = 7The DP Formulation
This time we're looking for the best answer, so we take the minimum of the two incoming directions instead of adding them:
State : dp[i][j] = minimum cost to reach (i, j) from (0, 0)
Recurrence : dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Base cases : dp[0][0] = grid[0][0]
first row → can only come from the left
first column → can only come from above
Answer : dp[m-1][n-1]Filling the table:
grid dp
1 3 1 1 4 5
1 5 1 2 7 6
4 2 1 6 8 7 ← answer
dp[1][1] = 5 + min(4, 2) = 7
dp[1][2] = 1 + min(5, 7) = 6
dp[2][2] = 1 + min(6, 8) = 7Recovering the Actual Path
Interviewers often follow up with: "Can you also print the path?"
The table already has all the information. Start at the bottom-right cell and walk backwards. At each cell, move to whichever neighbour (above or left) has the smaller dp value, because that's where the best path came from.
static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[0][0];
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] + grid[i][j];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] + grid[i][j];
} else {
dp[i][j] = grid[i][j]
+ Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Walk back from the bottom-right cell to recover the path
List<String> path = new ArrayList<>();
int i = m - 1;
int j = n - 1;
while (i > 0 || j > 0) {
path.add("(" + i + "," + j + ")");
if (i == 0) {
j--;
} else if (j == 0) {
i--;
} else if (dp[i - 1][j] <= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
path.add("(0,0)");
Collections.reverse(path);
System.out.println("Path taken : " + String.join(" -> ", path));
return dp[m - 1][n - 1];
}This prints (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2), which is the path 1 → 3 → 1 → 1 → 1.
This "walk back through the table" technique is called path reconstruction. You'll use it again for knapsack (which items were picked) and LCS (which characters match).
Problem 4: Triangle
Given a triangle of numbers, find the minimum path sum from top to bottom. From a position in one row, you can move to the same index or index + 1 in the next row.
2
3 4
6 5 7
4 1 8 3
Best path: 2 → 3 → 5 → 1 = 11Go Bottom-Up, Literally
If we go top-down, the last row has many possible ending points, and we have to take the minimum of all of them at the end. A cleaner trick is to start from the bottom row and move up:
State : dp[r][c] = minimum path sum from (r, c) down to the bottom
Recurrence : dp[r][c] = triangle[r][c] + min(dp[r+1][c], dp[r+1][c+1])
Base case : dp[last row] = the last row itself
Answer : dp[0][0] (the top, a single cell)Working upwards:
Start (last row) : [4, 1, 8, 3]
Row 2 (6, 5, 7) : [6+min(4,1), 5+min(1,8), 7+min(8,3)] = [7, 6, 10]
Row 1 (3, 4) : [3+min(7,6), 4+min(6,10)] = [9, 10]
Row 0 (2) : [2+min(9,10)] = [11] ← answerEach row only needs the row below it, so we can reuse a single 1D array:
static int minimumTotal(int[][] triangle) {
int rows = triangle.length;
int[] dp = triangle[rows - 1].clone();
for (int r = rows - 2; r >= 0; r--) {
for (int c = 0; c <= r; c++) {
dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);
}
}
return dp[0];
}Overwriting dp[c] is safe because, while moving left to right, dp[c] and dp[c + 1] still hold the values from the row below at the moment we read them.
Complexity: Time O(n²) for n rows (about n²/2 cells), Space O(n).
Problem 5: Maximal Square
Given a matrix of '0's and '1's, find the area of the largest square that contains only '1's.
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0The largest all-1 square is 2 × 2 (for example, rows 1–2 and columns 3–4, counting from 0), so the area is 4.
The DP Formulation
State : dp[i][j] = side length of the largest all-1 square
whose BOTTOM-RIGHT corner is at (i, j)
Recurrence : if cell is '1':
dp[i][j] = 1 + min(dp[i-1][j], ← above
dp[i][j-1], ← left
dp[i-1][j-1]) ← diagonal
if cell is '0':
dp[i][j] = 0
Answer : (max dp value)²Why the minimum of three? A square of side k ending at (i, j) needs squares of side k - 1 ending above it, to its left, and diagonally above-left. The smallest of those three limits how big the square can grow.
dp[i-1][j-1] dp[i-1][j]
2 2
dp[i][j-1] dp[i][j]
2 1 + min(2, 2, 2) = 3The table for our matrix:
matrix dp
1 0 1 0 0 1 0 1 0 0
1 0 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 2 2
1 0 0 1 0 1 0 0 1 0
Largest side = 2 → area = 4A neat trick in the code: we make the table one row and one column bigger ((m + 1) × (n + 1)) so that row 0 and column 0 are all zeros. This removes the need for special first-row and first-column checks.
static int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1]; // extra row/col of zeros
int side = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
side = Math.max(side, dp[i][j]);
}
}
}
return side * side;
}This padding trick is very common in 2D DP, and you'll see it again with strings.
Complete Java Program
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Main {
// 1. Unique Paths
static long uniquePaths(int m, int n) {
long[][] dp = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
// 2. Unique Paths with Obstacles (1 = blocked)
static int uniquePathsWithObstacles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dp[i][j] = 0;
} else if (i == 0 && j == 0) {
dp[i][j] = 1;
} else {
int fromTop = (i > 0) ? dp[i - 1][j] : 0;
int fromLeft = (j > 0) ? dp[i][j - 1] : 0;
dp[i][j] = fromTop + fromLeft;
}
}
}
return dp[m - 1][n - 1];
}
// 3. Minimum Path Sum (with path reconstruction)
static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[0][0];
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] + grid[i][j];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] + grid[i][j];
} else {
dp[i][j] = grid[i][j]
+ Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Walk back from the bottom-right cell to recover the path
List<String> path = new ArrayList<>();
int i = m - 1;
int j = n - 1;
while (i > 0 || j > 0) {
path.add("(" + i + "," + j + ")");
if (i == 0) {
j--;
} else if (j == 0) {
i--;
} else if (dp[i - 1][j] <= dp[i][j - 1]) {
i--;
} else {
j--;
}
}
path.add("(0,0)");
Collections.reverse(path);
System.out.println("Path taken : " + String.join(" -> ", path));
return dp[m - 1][n - 1];
}
// 4. Triangle (bottom-up, 1D array)
static int minimumTotal(int[][] triangle) {
int rows = triangle.length;
int[] dp = triangle[rows - 1].clone();
for (int r = rows - 2; r >= 0; r--) {
for (int c = 0; c <= r; c++) {
dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);
}
}
return dp[0];
}
// 5. Maximal Square
static int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m + 1][n + 1];
int side = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
Math.min(dp[i - 1][j], dp[i][j - 1]));
side = Math.max(side, dp[i][j]);
}
}
}
return side * side;
}
public static void main(String[] args) {
System.out.println("Unique paths 3 x 3 : " + uniquePaths(3, 3));
System.out.println("Unique paths 3 x 7 : " + uniquePaths(3, 7));
int[][] obstacles = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
System.out.println("Paths with obstacle : " + uniquePathsWithObstacles(obstacles));
int[][] grid = {
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
};
System.out.println("Minimum path sum : " + minPathSum(grid));
int[][] triangle = {
{2},
{3, 4},
{6, 5, 7},
{4, 1, 8, 3}
};
System.out.println("Triangle minimum : " + minimumTotal(triangle));
char[][] matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
System.out.println("Maximal square area : " + maximalSquare(matrix));
}
}Output:
Unique paths 3 x 3 : 6
Unique paths 3 x 7 : 28
Paths with obstacle : 2
Path taken : (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)
Minimum path sum : 7
Triangle minimum : 11
Maximal square area : 4Notice that "Path taken" is printed before "Minimum path sum". That's because minPathSum() prints the path while it runs, and only then does main print the returned value.
Space Optimization: From 2D to 1D
Look at the Unique Paths recurrence again:
dp[i][j] = dp[i-1][j] + dp[i][j-1]Each cell needs only the row above and the current row. Older rows are never used again.
So we can keep a single 1D array row of size n:
Before updating,
row[j]still holds the value from the row above (that'sdp[i-1][j]).row[j - 1]was already updated in this pass (that'sdp[i][j-1]).
static long uniquePathsOptimized(int m, int n) {
long[] row = new long[n];
Arrays.fill(row, 1); // first row is all 1s
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
row[j] = row[j] + row[j - 1]; // above + left
}
}
return row[n - 1];
}uniquePathsOptimized(3, 7) also returns 28.
Space drops from O(m × n) to O(n). The same trick works for Minimum Path Sum and many other grid problems.
The trade-off: once you compress to 1D, you lose the full table, so you can't reconstruct the path anymore. If the problem asks for the path, keep the 2D table.
Choosing the Right Recurrence
Problem | Combine Using | Recurrence |
|---|---|---|
Unique Paths | Sum (count ways) |
|
Paths with Obstacles | Sum, but 0 on blocked cells |
|
Minimum Path Sum | Min (best cost) |
|
Triangle | Min, from the bottom up |
|
Maximal Square | Min of three neighbours + 1 |
|
The most important question in every grid problem is: "From which cells can I arrive at this cell?" Those cells are exactly what the recurrence reads.
Common Mistakes
1. Forgetting the first row and first column
Cells in row 0 have no cell above them, and cells in column 0 have no cell to their left. Accessing dp[-1][j] throws ArrayIndexOutOfBoundsException. Either handle them separately or pad the table with an extra row and column.
2. Wrong filling order
If a cell depends on the cell above and the cell to the left, you must fill top-to-bottom and left-to-right. In the Triangle problem, the dependency goes the other way (on the row below), so you fill bottom-to-top.
3. Mixing up rows and columns
grid.length is the number of rows and grid[0].length is the number of columns. Swapping them works for square grids but crashes on rectangular ones, so always test a non-square grid.
4. Overflow in counting problems
Path counts grow very fast. Use long, or take the result modulo 10⁹ + 7 when the problem asks for it.
5. Space-optimizing when the path is needed
Compressing to one row is great for the final number, but it destroys the information needed to reconstruct the path.
Practice Problems
Unique Paths (LeetCode 62)
Unique Paths II (LeetCode 63)
Minimum Path Sum (LeetCode 64)
Triangle (LeetCode 120)
Maximal Square (LeetCode 221)
Minimum Falling Path Sum (LeetCode 931)
Dungeon Game (LeetCode 174)
Cherry Pickup (LeetCode 741), an advanced one
The Main Idea
2D Dynamic Programming is used when a state needs two variables to describe it. The answers live in a table dp[i][j].
For grid problems, the recipe is:
1. dp[i][j] = answer for reaching (or starting from) cell (i, j)
2. Ask: from which neighbouring cells can I arrive here?
3. Combine those neighbours with +, min, or max
4. Handle the first row / first column (or pad the table)
5. Fill in an order where the neighbours are always readyThe complexity is usually:
Time → O(rows × columns)
Space → O(rows × columns), often reducible to O(columns)A 2D DP table is just a grid of small answers. Each cell is built from a few neighbouring cells that were filled before it.
In the next chapter, we'll use exactly the same 2D table idea for a different kind of problem, where the two dimensions are items and capacity: the famous Knapsack Problems.