Longest Common Subsequence
# Longest Common Subsequence
# Problem Formulation
Idea: The longest common subsequence up to certain position $i$ in the first sequence and $j$ in another sequence, can be found using the longest common sub sequences of the sequences up till $i-1$ and $j-1$.
The base case when either subsequence is empty, there will not be any common characters: $$LCS(i,j)=0 $$
Common character found at (i,j):
$$LCS(i,j)= LCS(i-1,j-1)+1 $$
No common character at position (i,j):
$$LCS(i,j)=max(LCS(i-1,j), LCS(i,j-1)) $$
# Strategy
# Pseudocode
# Examples: Obtaining the subsequence characters
