2D DP

Grid-Based DP Problems

Grid DP problems involve finding optimal paths or counts in a 2D grid.

Unique Paths

// Count paths from top-left to bottom-right (only right/down moves)
public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    // Base cases: first row and first column have 1 path each
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    
    // Fill the grid
    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];  // From top + from left
        }
    }
    
    return dp[m - 1][n - 1];
}

// Space-optimized: O(n) space
public int uniquePathsOptimized(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];  // dp[j] (from top) + dp[j-1] (from left)
        }
    }
    
    return dp[n - 1];
}

Minimum Path Sum

// Find path with minimum sum from top-left to bottom-right
public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;  // Start cell
            else if (i == 0) grid[i][j] += grid[i][j - 1];  // First row
            else if (j == 0) grid[i][j] += grid[i - 1][j];  // First column
            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    
    return grid[m - 1][n - 1];
}

Unique Paths with Obstacles

// Grid with obstacles (1 = obstacle, 0 = empty)
public int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    
    if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return 0;
    
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
    
    for (int i = 1; i < m; i++) {
        dp[i][0] = (grid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = (grid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (grid[i][j] == 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    return dp[m-1][n-1];
}

Key Pattern for Grid DP

// State: dp[i][j] = optimal value at cell (i,j)
// Transition: dp[i][j] = f(dp[i-1][j], dp[i][j-1])  // for 4-directional
// Or: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])  // for diagonal

Space Optimization for Grid DP

// If transition only depends on previous row, use single row
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (i == 0 && j == 0) dp[j] = grid[0][0];
        else if (i == 0) dp[j] = dp[j-1] + grid[0][j];
        else if (j == 0) dp[j] = dp[j] + grid[i][0];
        else dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
    }
}
return dp[n-1];

String DP Problems

String DP problems involve comparing or transforming two strings.

Longest Common Subsequence (LCS)

// Find length of longest common subsequence of two strings
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;  // Characters match
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // Skip one
            }
        }
    }
    
    return dp[m][n];
}

// Space-optimized: O(n) space
public int lcsOptimized(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[] dp = new int[n + 1];
    
    for (int i = 1; i <= m; i++) {
        int prev = 0;  // dp[i-1][j-1]
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

Edit Distance

// Minimum operations to convert word1 to word2
// Operations: insert, delete, replace
public int editDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // Base cases: converting empty string
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // Delete all
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // Insert all
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];  // No operation needed
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1],  // Replace
                    Math.min(dp[i - 1][j],   // Delete
                             dp[i][j - 1])    // Insert
                );
            }
        }
    }
    
    return dp[m][n];
}

Longest Palindromic Subsequence

// Find longest palindromic subsequence in a string
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    
    // Base case: single character
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    
    // Fill for lengths 2 to n
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[0][n - 1];
}

String DP Patterns

Problem	State	Transition
LCS	dp[i][j] = LCS of s1[0..i-1], s2[0..j-1]	match: dp[i-1][j-1]+1, else: max(dp[i-1][j], dp[i][j-1])
Edit Distance	dp[i][j] = ops to convert s1[0..i-1] to s2[0..j-1]	match: dp[i-1][j-1], else: 1+min(replace, delete, insert)
Palindrome	dp[i][j] = LPS in s[i..j]	match: dp[i+1][j-1]+2, else: max(dp[i+1][j], dp[i][j-1])

Practice Problems

0/1solved

MediumLongest Common Subsequence

2D String DP

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example:

Input: text1 = "abcde", text2 = "ace"

Output: 3

The longest common subsequence is "ace" and its length is 3.

Optimal Solution — O(m * n) time, O(m * n), can be optimized to O(min(m, n)) space

2D DP where dp[i][j] is LCS length of text1[0..i-1] and text2[0..j-1]. If characters match, extend LCS; otherwise, take max of skipping one character from either string.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        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)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
}

Edge Cases:

One or both strings are empty
Strings are identical
No common characters
One string is subsequence of the other

Flashcards

Question

What is the state transition for Edit Distance?

Click to reveal answer

Answer

If chars match: dp[i][j] = dp[i-1][j-1]. Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) representing replace, delete, insert.

Question

How do you optimize 2D DP space from O(m*n) to O(n)?

Click to reveal answer

Answer

When dp[i][j] only depends on current and previous row, use a single 1D array and update carefully left-to-right or right-to-left.

Question

What is 2D Dynamic Programming?

Click to reveal answer

Answer

2D Dynamic Programming is a key concept in software engineering.

Question

When to use 2D Dynamic Programming?

Click to reveal answer

Answer

Use 2D Dynamic Programming when building production systems that require reliability, scalability, and maintainability.

Question

2D Dynamic Programming best practices

Click to reveal answer

Answer

Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.

Revision Notes

Key Takeaways

1.Grid DP: dp[i][j] depends on neighbors (top, left, diagonal)
2.String DP: dp[i][j] depends on comparing characters at positions i-1, j-1
3.Space optimization uses single row when only previous row needed
4.Always handle base cases for first row and first column

Interview Tips

•Draw out small examples to understand state transitions
•Clarify if subsequence (non-contiguous) or substring (contiguous)
•Discuss space optimization after giving O(mn) solution
•For Edit Distance, explain the three operations clearly

Cheat Sheet

2D DP Cheat Sheet

Grid DP Patterns:

Unique paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Min path sum: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
Obstacles: set dp[i][j] = 0 when obstacle

String DP Patterns:

LCS: match: dp[i-1][j-1]+1, else: max(dp[i-1][j], dp[i][j-1])
Edit Distance: match: dp[i-1][j-1], else: 1+min(replace, delete, insert)
Palindrome: match: dp[i+1][j-1]+2, else: max(dp[i+1][j], dp[i][j-1])

Space Optimization:

Use single row when transition depends on previous row only
Update direction matters (left-to-right vs right-to-left)

Base Cases:

First row/column usually initialized to 1 or 0
Empty string comparisons: dp[0][j] = j, dp[i][0] = i

Grid-Based DP Problems

Unique Paths

Minimum Path Sum

Unique Paths with Obstacles

Key Pattern for Grid DP

Space Optimization for Grid DP

String DP Problems

Longest Common Subsequence (LCS)

Edit Distance

Longest Palindromic Subsequence

String DP Patterns

Practice Problems

Quiz

Flashcards

Revision Notes

Key Takeaways

Interview Tips

Cheat Sheet

2D DP Cheat Sheet