2D Dynamic Programming

Think of your career and personal life as two dimensions on a grid. Every move along one axis echoes across the other.

You've seen how 1D DP can solve problems by breaking them into a sequence of smaller subproblems. 2D DP extends this to problems where the state depends on two changing parameters, often involving grids, matrices, or comparing two strings.

Problem: Unique Paths (LeetCode Link): A robot is in an m x n grid at the top-left corner. It can only move down or right. How many possible unique paths are there to the bottom-right corner? 💡 Hint

From 1D to 2D DP

Just like with 1D DP, let's first think recursively. The number of ways to reach cell (r, c) is the sum of the ways to reach the cells we could have come from - top and left: paths(r, c) = paths(r-1, c) + paths(r, c-1)

Again, a naive recursive solution would be incredibly slow due to massive overlapping subproblems. The solution is to use a 2D table (a grid) to store the results of these subproblems.

The Tabulation (Bottom-Up) Approach

This is the most common and intuitive way to solve 2D DP problems.

Define DP State: We'll create a 2D array, dp, where dp[r][c] stores the number of unique paths to reach the cell at (row, col).
Base Cases: How many ways are there to reach any cell in the first row? Only one: by moving right from the start. The same is true for the first column; there's only one way to reach each cell by moving down. So, we initialize dp[r][0] = 1 for all r and dp[0][c] = 1 for all c.
Recurrence Relation: For any other cell (r, c), the recurrence is dp[r][c] = dp[r-1][c] + dp[r][c-1].
Iteration: We loop through the grid, starting from (1, 1), and fill in the dp table. The final answer will be in the bottom-right cell, dp[m-1][n-1].

Walkthrough: Filling the DP Table

Imagine a 3x3 grid.

Initialize the dp table:

[ [1, 1, 1],
  [1, 0, 0],
  [1, 0, 0] ]

Calculate dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2.
Calculate dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3.
...and so on, until the table is full. The final answer for a 3x3 grid is dp[2][2] = 6.

def unique_paths(m: int, n: int) -> int:
    # dp[r][c] = number of paths to reach (r, c)
    dp = [[1] * n for _ in range(m)]

    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
            
    return dp[m-1][n-1]

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // Base cases: initialize first row and column to 1
    for (int r = 0; r < m; r++) dp[r][0] = 1;
    for (int c = 0; c < n; c++) dp[0][c] = 1;

    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] = dp[r-1][c] + dp[r][c-1];
        }
    }
    return dp[m-1][n-1];
}

int uniquePaths(int m, int n) {
    std::vector<std::vector<int>> dp(m, std::vector<int>(n, 1));

    for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            dp[r][c] = dp[r-1][c] + dp[r][c-1];
        }
    }
    return dp[m-1][n-1];
}

Space Optimization Just like in 1D DP, you can often optimize the space. For "Unique Paths," notice that to compute the current row dp[r], you only need the values from the previous row, dp[r-1]. You don't need the entire m x n grid in memory. This means you can optimize the space complexity from $O(M*N)$ to $O(N)$ by only storing one or two rows at a time.

Try it Yourself: Can you try to implement the top-down DP approach with memoization yourself?

2D Dynamic Programming

From 1D to 2D DP

The Tabulation (Bottom-Up) Approach

Walkthrough: Filling the DP Table

More Problems & Variations