2D DP

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