Chapter 62 of 65

2D Dynamic Programming

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 . .
. . .
. . E

There are 6 paths. Two of them are:

Right → Right → Down → Down
Down → Right → Down → Right

Think 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  ← answer

Each 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 0

The 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  ← answer
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];
}

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 1

The best path is:

1 → 3 → 1
        ↓
        1
        ↓
        1

Total = 1 + 3 + 1 + 1 + 1 = 7

The 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) = 7

Recovering 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 = 11

Go 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]  ← answer

Each 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 0

The 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) = 3

The 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 = 4

A 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   : 4

Notice 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's dp[i-1][j]).

  • row[j - 1] was already updated in this pass (that's dp[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)

dp[i-1][j] + dp[i][j-1]

Paths with Obstacles

Sum, but 0 on blocked cells

blocked ? 0 : dp[i-1][j] + dp[i][j-1]

Minimum Path Sum

Min (best cost)

grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Triangle

Min, from the bottom up

t[r][c] + min(dp[r+1][c], dp[r+1][c+1])

Maximal Square

Min of three neighbours + 1

1 + min(up, left, diagonal)

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 ready

The 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.