logest common subsequence(LCS)

Q: find the longest common subsequence of string X, Y
X: ab c bdab
Y: bdcab a

--
An example about the dynamic programming.

review the four steps of dynamic programming
1. optimal substrucutre
f[i,j]: lcs of seq 1 of size i, and seq 2 of size j

2. recursive formulation
f[i,j] = 0 if i = 0 or j = 0
c[i-1, j-1]+1 if i,j > 0 and Xi = Yj
max(c[i-1,j],c[i,j-1]) if i,j > 0 and Xi != Yj

3.compute optimal value
4.contruct an optimal solution(optional)