Dynamic Programming

Longest Common Subsequence (LCS)

Problem Formulation

• Input: Arrays $A[1\dots n]$ and $B[1\dots m]$ of characters
• Output: The maximum length $k$ of a common subsequence to $A$ and $B$ (subsequences do not need to be contiguous)

We break this down into a subproblems indexed at $i,j$, where we want to find the LCS of $A[1\dots i]$ and $B[1\dots j]$. We notice that there are 3 cases:

1. If $A[i]=B[j]$, then the longest common subsequence must include these letter (since they are the last letters). Other common letters can be found in $A[1\dots i-1]$ and
   • $dp[i,j]=1+dp[i-1,j-1]$
2. Else, we have that $A[i]\ne B[j]$. If $A[i]$ is not in the subsequence, then we search for $A[1\dots i-1]$ and $B[1\dots j]$. Else if $B[j]$ is not in the subsequence, we search in $A[1\dots i]$ and $B[1\dots j-1]$.
   • $dp[i,j]=max(dp[i-1,j],dp[i,j-1])$

For our base cases, we have $dp[0,j]=0$ and $dp[i,0]=0$ (longest subsequence of empty string is 0).

This i

Related

• Longest Increasing Subsequence