Longest Common Subsequence

题目：

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example: For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

分析：

1. state: f[i][j] the longest LCS in first i of A and j of B
2. function:
    if (A[i - 1] == B[j - 1]) {
        f[i][j] = max(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] + 1);
    } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    }
3. init: f[0][0] = f[0][1] = f[1][0] = 0;
4. answer: f[m][n]

解法：

class Solution {
public:
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    int longestCommonSubsequence(string A, string B) {
        // write your code here
        int m = A.size();
        int n = B.size();
        if (m == 0 || n == 0) {
            return 0;
        }
        vector<vector<int> > f(m + 1, vector<int>(n + 1, 0) );

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A[i - 1] == B[j - 1]) {
                    f[i][j] = max(max(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1] + 1);
                } else {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        return f[m][n];
    }
};