IntermediateDynamic Programming

Subsequence DP

DP over sequences for edit distance, LCS, and palindromic subsequences

Time: O(nm)
Space: O(nm) or O(min(n,m))
Pattern Overview

Core Idea

dp[i][j] compares prefixes up to i, j; transitions depend on equal/mismatch cases.

When to Use

Use when aligning two strings or reverse of one string.

General Recognition Cues
General indicators that this pattern might be applicable
  • Two strings
  • Insert/delete/replace
  • Longest common/palindrome
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Edit Distance

Min ops convert s→t

When to Use This Variant
  • Insert/delete/replace
Use Case
Transform cost
Advantages
  • Classic DP
Implementation
def edit_distance(s, t):
    n,m=len(s),len(t); dp=[[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0]=i
    for j in range(m+1): dp[0][j]=j
    for i in range(1,n+1):
        for j in range(1,m+1):
            if s[i-1]==t[j-1]: dp[i][j]=dp[i-1][j-1]
            else: dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]
2

LCS

Longest common subsequence

When to Use This Variant
  • Match then diag
Use Case
Similarity
Advantages
  • O(nm)
Implementation
def lcs(s, t):
    n,m=len(s),len(t); dp=[[0]*(m+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[i][j]=dp[i-1][j-1]+1 if s[i-1]==t[j-1] else max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]
3

Palindromic Subsequence

LPS via reverse or 2D DP

When to Use This Variant
  • Palindrome
Use Case
String analysis
Advantages
  • Reuses LCS idea
Implementation
def lps(s):
    t=s[::-1]; return lcs(s,t)
Common Pitfalls
Watch out for these common mistakes
  • Initialization of dp[0][*] rows/cols
  • Index shifts
  • Memory O(nm) too big
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(nm)

Table fill.

Space Complexity
O(nm) or O(min(n,m))

Row/col compression possible.

Ready to test your knowledge?

Test your pattern recognition with interactive questions