🧠 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 Ins…


This content originally appeared on DEV Community and was authored by DevCorner2

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

💬 Want Another Master Template?

You now have:

  1. Backtracking Template
  2. Take/Not Take DP
  3. DP on Strings / Sequences

Other powerful master patterns I can provide:

  • Grid DP (Pathfinding, Min Path Sum)
  • Partition DP (Matrix Chain, Palindrome Partitioning)
  • Bitmask DP (TSP, Subset Problems)
  • Digit DP (Constraints on Numbers)
  • Monotonic Stack / Sliding Window Optimization
  • State-Driven Graph DP (DP + BFS/DFS)


This content originally appeared on DEV Community and was authored by DevCorner2


Print Share Comment Cite Upload Translate Updates
APA

DevCorner2 | Sciencx (2025-07-29T05:38:54+00:00) 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences. Retrieved from https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/

MLA
" » 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences." DevCorner2 | Sciencx - Tuesday July 29, 2025, https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/
HARVARD
DevCorner2 | Sciencx Tuesday July 29, 2025 » 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences., viewed ,<https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/>
VANCOUVER
DevCorner2 | Sciencx - » 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/
CHICAGO
" » 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences." DevCorner2 | Sciencx - Accessed . https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/
IEEE
" » 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences." DevCorner2 | Sciencx [Online]. Available: https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/. [Accessed: ]
rf:citation
» 🧠 MASTER TEMPLATE #2: DP on Strings / Sequences | DevCorner2 | Sciencx | https://www.scien.cx/2025/07/29/%f0%9f%a7%a0-master-template-2-dp-on-strings-sequences/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts