## other: Longest common subsequence

http://lintcode.com/en/problem/longest-common-subsequence/
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

--------------------------
print the length of the longest common sub-sequence
DP
The actual sequence can be generated by using backtrack.
Reference:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

int lcs (string a, string b) {
    int m = a.length();
    int n = b.length();
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            if (a[i] == b[i]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
} 

-------------------------------------------------
Recursion

int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}