2D Dynamic Programming

1. Introduction: Escaping the Grid

If 1D DP answers the question "How do I get to the end of a line?", 2D DP answers the question "How do I get across this map?"

In 2D Dynamic Programming, the state of the problem cannot be represented by a single integer. Usually, you are navigating a 2D matrix (like a robot on a grid) or comparing two separate arrays/strings (like finding the Longest Common Subsequence). Because the state requires two variables (e.g., row and col, or index1 and index2), we cache our results in a 2D array: dp[M][N].

These problems heavily feature in technical interviews because they combine the boundary-management skills of matrix traversal with the mathematical logic of DP.

2. Core Concept: The 2D State Machine

When writing a 2D DP solution, you follow the same rules as 1D DP, but your transitions involve multiple dimensions.

1. State Definition: What does dp[i][j] represent? (e.g., "The minimum cost to reach cell (i, j)").
2. Base Cases: What happens at the starting cell dp[0][0]? What about the top row and left column where movement is restricted?
3. Transition Equation: How do we calculate dp[i][j] from its neighbors? Usually, you look at where you could have come from. If you can only move Down and Right, then to reach (i, j), you must have come from (i-1, j) (above) or (i, j-1) (left). So, dp[i][j] = cost[i][j] + Math.min(dp[i-1][j], dp[i][j-1]).

3. Beginner Code Example: Unique Paths

Problem Statement: (LeetCode 62) A robot is located at the top-left corner of an $m \times n$ grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. How many possible unique paths are there?

The Insight: To reach cell (i, j), you MUST have come from (i-1, j) or (i, j-1). Therefore, the number of ways to reach (i, j) is the number of ways to reach the cell above it PLUS the number of ways to reach the cell to its left!

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        
        // Base Case: The first row and first column only have ONE way to be reached
        // (By moving strictly right, or strictly down).
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        
        // Build the table
        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]; // Return the bottom-right corner
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$ to fill the grid.
• Space Complexity: $O(M \times N)$ for the DP matrix.

4. Intermediate Code Example: Minimum Path Sum

Problem Statement: (LeetCode 64) Given an $m \times n$ grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. You can only move down or right.

This is exactly like Unique Paths, but instead of adding the previous paths, we take the minimum cost of the two previous paths and add the current cell's cost.

public class MinPathSum {
    public static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        // Base Case: Starting cell
        dp[0][0] = grid[0][0];
        
        // Base Case: Top row (can only come from the left)
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        
        // Base Case: Left column (can only come from above)
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        
        // Transition: Pick the cheaper route
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

5. Advanced Code Example: Longest Common Subsequence (LCS)

Problem Statement: (LeetCode 1143) Given two strings text1 and text2, return the length of their longest common subsequence. Example: text1 = "abcde", text2 = "ace". Output: 3 (The sequence is "ace").

This is the grandfather of all String DP problems. Our 2D matrix isn't a physical grid; it's a comparison matrix where rows represent characters in text1 and columns represent characters in text2.

The State: dp[i][j] represents the LCS length between the first i characters of text1 and the first j characters of text2.

The Transition:

• If text1[i-1] == text2[j-1]: The characters match! We extend the LCS from the previous subproblem. dp[i][j] = 1 + dp[i-1][j-1].
• If they do NOT match: The longest sequence must come from either ignoring the current character of text1, or ignoring the current character of text2. We take the max! dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

public class LCS {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // We use size m+1 and n+1. 
        // The 0th row/col represents comparing with an empty string (which is always 0).
        // This cleverly avoids array out-of-bounds checks!
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Match found: Diagonal + 1
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // No match: Max of Top or Left
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$.
• Space Complexity: $O(M \times N)$ for the DP table. (Can be optimized to $O(\min(M, N))$ by only keeping two rows).

6. Common Mistakes Beginners Make

1. Not padding the DP table (Size N+1)

   • The Mistake: Initializing dp = new int[m][n] for string comparison problems, and manually writing dozens of if (i > 0 && j > 0) boundary checks.
   • Why it's wrong: It clutters the code and invites IndexOutOfBounds exceptions.
   • The Fix: Always use an (M+1) x (N+1) matrix. The 0 index acts as a dummy base-case (like an empty string or empty prefix) holding 0s, making the for loops beautifully clean.

2. Mixing up row and column dimensions

   • The Mistake: Traversing dp[j][i] instead of dp[i][j].
   • Why it's wrong: A matrix in Java is an array of arrays. If it is non-square ($M \neq N$), flipping indices instantly crashes the program.

3. Thinking 2D Space is mandatory

   • The Mistake: Leaving the Space Complexity at $O(M \times N)$ in an interview without mentioning optimization.
   • The Fix: Notice that in almost all 2D DP, dp[i][j] only relies on dp[i-1] (the row above) or dp[i] (the current row). You NEVER need the entire matrix. You can reduce $O(M \times N)$ space down to $O(N)$ space by simply keeping an int[] prevRow and int[] currentRow.

7. Interview Q&A

Q1: How do you trace the actual path in Unique Paths or the actual string in LCS? Answer: To reconstruct the path/string, you start at the bottom-right cell dp[m][n]. You look at the values of its neighbors. For LCS, if dp[i][j] == dp[i-1][j-1] + 1 and the characters matched, you add the character to your result and move diagonally up-left. Otherwise, move to the neighbor with the larger DP value. Repeat until you hit 0.

Q2: What is the Edit Distance (Levenshtein Distance) problem? Answer: It is an extension of LCS (LeetCode 72). Instead of just finding common characters, you find the minimum number of insertions, deletions, and substitutions to turn Word A into Word B. The transition equation involves taking the min of the top, left, and diagonal cell!

Q3: Can 2D DP be parallelized? Answer: Not easily. Because dp[i][j] inherently depends on its left and top neighbors, you cannot compute the grid randomly. However, you can compute the grid across its diagonals in parallel, because cells on the same diagonal do not depend on each other!

8. Practice Problems

1. Unique Paths II (LeetCode 63)
   • Goal: Same as Unique Paths, but the grid contains obstacles. If a cell is an obstacle, dp[i][j] = 0.
2. Edit Distance (LeetCode 72)
   • Hint: The ultimate string DP problem. Three choices: Insert (Left), Delete (Top), Replace (Diagonal).
3. Maximal Square (LeetCode 221)
   • Hint: dp[i][j] represents the side length of the maximum square whose bottom right corner is at (i, j). dp[i][j] = min(top, left, top-left) + 1.

9. Summary

• 2D Grids: Used for pathfinding and string comparisons.
• Base Cases Matter: In physical grids, the top row and left column usually require separate initialization because they can only be reached from one direction.
• The Padding Trick: For string comparisons, always use an (M+1) x (N+1) matrix to avoid boundary crashes.
• Space Optimization: The interviewer will almost always ask if you can optimize the space. If you only look up one row, you only need to store one row!