CodeMosa

Master LeetCode Patterns

IntermediateDynamic ProgrammingRead Dynamic Programming Fundamentals →

Subsequence DP

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

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

What is Subsequence DP?

#
Definition: 2D DP over prefixes of sequences with transitions based on character matches/mismatches.

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.

How Subsequence DP works

#

2D DP over prefixes with match/mismatch transitions (edit distance/LCS/LPS); compress to 1D by scanning in the correct order.

  • Two strings
  • Insert/delete/replace
  • Longest common/palindrome

General Recognition Cues

#
General indicators that this pattern might be applicable
  • Two strings
  • Insert/delete/replace
  • Longest common/palindrome

Related Collections

#
Curated practice sets for this pattern
Dynamic Programming Problems

Code Templates

#
2D DP over prefixes with match/mismatch transitions (edit distance/LCS/LPS); compress to 1D by scanning in the correct order.
# Knapsack Templates (0/1)
def knapsack_01(weights, values, W):
    dp=[0]*(W+1)
    for w,v in zip(weights, values):
        for c in range(W, w-1, -1):
            dp[c]=max(dp[c], dp[c-w]+v)
    return dp[W]

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

Related Patterns

#
1D DP2D Grid DPBitmask DPDigit DPInterval DPKnapsack

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