🧠 MASTER TEMPLATE #2: DP on Strings / Sequences

Applies to all problems involving two sequences, edit distances, transformations, or comparisons.

✅ What It Solves

Longest Common Subsequence (LCS)
Longest Palindromic Subsequence (LPS)
Edit Distance (Levenshtein Distance)
Minimum Insertions/Deletions
Sequence Alignment
Wildcard Matching
String Interleaving
Regex Matching

🔧 Core Structure: DP[i][j] = answer for first i chars of A and first j chars of B

// Memoization: Top-Down Recursive Template
int dp(int i, int j, String a, String b, int[][] memo) {
    if (i == a.length() || j == b.length()) return base_case;

    if (memo[i][j] != -1) return memo[i][j];

    if (a.charAt(i) == b.charAt(j)) {
        return memo[i][j] = 1 + dp(i + 1, j + 1, a, b, memo);
    } else {
        return memo[i][j] = Math.max(
            dp(i + 1, j, a, b, memo),
            dp(i, j + 1, a, b, memo)
        );
    }
}

🧱 Bottom-Up (Tabulation)

int lcs(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (a.charAt(i) == b.charAt(j))
                dp[i][j] = 1 + dp[i + 1][j + 1];
            else
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j + 1]);
        }
    }

    return dp[0][0];
}

🔀 Edit Distance Variant (Min Operations)

int editDistance(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];

    for (int i = 0; i <= a.length(); i++) {
        for (int j = 0; j <= b.length(); j++) {
            if (i == 0) dp[i][j] = j;
            else if (j == 0) dp[i][j] = i;
            else if (a.charAt(i - 1) == b.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[a.length()][b.length()];
}

🔍 When to Use This Template

Problem Type	Key Signs
LCS family	Comparing or aligning two strings/sequences
Palindrome problems	String → reversed string (transform to LCS)
Distance calculation	Count of operations (edit/insert/delete)
Regex/wildcard	Pattern matching with `*`, `?`, etc.
Merge/Interleave	Construct string using two sequences

📌 Common Tricks

Reverse the string to find LPS using LCS
Use 1D DP to optimize space if only dp[i][j+1] and dp[i+1][j] are used
For Edit Distance, careful handling of insert/delete costs

🛠️ Abstract DP Signature

// Memoization
int dp(int i, int j, String a, String b, DP[][] memo);

// Tabulation
dp[i][j] = recurrence based on a[i-1] == b[j-1]

🧠 TL;DR Summary

Problem	Base Case	Recurrence Relation
LCS	i == n or j == m	if match: 1 + dp(i+1,j+1) else max(dp(i+1,j), dp(i,j+1))
Edit Distance	i == 0 or j == 0	1 + min(insert, delete, replace)
Palindromic Subsequence	i > j	if match: 2 + dp(i+1,j-1), else max(dp(i+1,j), dp(i,j-1))
Wildcard Matching	i == lenA, j == lenB	branching on `*`, `?`, match