Sequence DP: Edit Distance and String Problems

Edit Distance (LeetCode 72)

Goal: Transform word1 into word2 using minimum operations (Insert, Delete, Replace).

State Definition

dp[i][j] = Minimum operations to convert prefix word1[0..i-1] to prefix word2[0..j-1].

Transition Logic

• If word1[i-1] == word2[j-1]: Characters match, no operation needed: dp[i][j] = dp[i-1][j-1].
• Else, take the minimum of three operations:
  • Replace: 1 + dp[i-1][j-1] (Transform word1[0..i-2] to word2[0..j-2], then replace the mismatch).
  • Delete: 1 + dp[i-1][j] (Transform word1[0..i-2] to word2[0..j-1], then delete word1[i-1]).
  • Insert: 1 + dp[i][j-1] (Transform word1[0..i-1] to word2[0..j-2], then insert word2[j-1]).

Initial Cases

• dp[0][j] = j (Empty word1 needs $j$ insertions).
• dp[i][0] = i (Empty word2 needs $i$ deletions).

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    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];
            } 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 Common Subsequence (LCS)

dp[i][j] = Length of LCS for suffixes of length $i$ and $j$.

public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.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];
}

Longest Palindromic Subsequence

dp[i][j] = Length of the longest palindromic subsequence within the range s[i..j] (Interval DP).

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1; // Single char is a palindrome of length 1
    
    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];
}

Distinct Subsequences (LeetCode 115)

How many subsequences of s are equal to t?

dp[i][j] = Count of subsequences of s[0..i-1] equal to t[0..j-1].

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = 1; // Empty 't' always matches (one way: pick nothing)
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= Math.min(i, n); j++) {
            dp[i][j] = dp[i - 1][j]; // Case: Don't use s[i-1]
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1]; // Case: Use s[i-1] to match t[j-1]
            }
        }
    }
    return dp[m][n];
}

Burst Balloons (Interval DP: LeetCode 312)

Inverse Thinking: Instead of picking the first balloon, decide which balloon is the last to be burst in a range.

dp[i][j] = Max coins obtained by bursting all balloons within the (open) interval (i, j).

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    System.arraycopy(nums, 0, arr, 1, n);
    
    int[][] dp = new int[n + 2][n + 2];
    for (int len = 2; len <= n + 1; len++) {
        for (int left = 0; left <= n + 1 - len; left++) {
            int right = left + len;
            for (int k = left + 1; k < right; k++) {
                // Bursting balloon 'k' at the end of (left, right) sequence
                dp[left][right] = Math.max(dp[left][right], 
                    dp[left][k] + arr[left] * arr[k] * arr[right] + dp[k][right]);
            }
        }
    }
    return dp[0][n + 1];
}

String DP Synthesis Table