dynamic programming

Longest Common Subsequence (LCS) problem
Seems like the editing distance that I learned from Information Retrieval.
The subsequence does not have to be a string in which one character is next to the other.
Using dynamic programming method, f[1][1]=same(1,1), the length of common subsequence can be calculated as f[i][j] = max(f[i-1][j-1]+(A[i]==B[j]), f[i-1][j],f[i][j-1])
The last element (also the biggest one) is the length of LCS.