# Longest Common Subsequence (LCS)

Problem Formulation

Input: Arrays $A[1…n]$ and $B[1…m]$ of charactersOutput: 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…i]$ and $B[1…j]$. We notice that there are 3 cases:

- 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…i−1]$ and
- $dp[i,j]=1+dp[i−1,j−1]$

- Else, we have that $A[i]=B[j]$. If $A[i]$ is not in the subsequence, then we search for $A[1…i−1]$ and $B[1…j]$. Else if $B[j]$ is not in the subsequence, we search in $A[1…i]$ and $B[1…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