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? 💡 HintTo get to any cell (r, c), where could the robot have been just one step before?

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.

1. 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).
2. 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.
3. Recurrence Relation: For any other cell (r, c), the recurrence is dp[r][c] = dp[r-1][c] + dp[r][c-1].
4. 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.

1. Initialize the dp table:

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

2. Calculate dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2.
3. Calculate dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3.
4. ...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?

More Problems & Variations

The key to 2D DP is defining what dp[i][j] represents.

1. Longest Common Subsequence (LeetCode Link): Given two strings, find the length of their longest common subsequence. 💡 HintLet dp[i][j] be the length of the LCS for the first i characters of text1 and the first j characters of text2. If text1[i] == text2[j], then dp[i][j] = 1 + dp[i-1][j-1]. Otherwise, you take the max of the previous states: max(dp[i-1][j], dp[i][j-1]).

2. Edit Distance (LeetCode Link): Find the minimum number of operations (insert, delete, replace) required to convert word1 to word2. 💡 HintLet dp[i][j] be the min distance between the first i chars of word1 and j chars of word2. If word1[i] == word2[j], no operation is needed, so dp[i][j] = dp[i-1][j-1]. Otherwise, you must perform one operation, so you take 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).