LintCode (77) Longest Common Subsequence

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

Your code should return the length of LCS.

Have you met this question in a real interview? 

Yes

Example

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

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

Clarification

What's the definition of Longest Common Subsequence?

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://baike.baidu.com/view/2020307.htm

属于二维dp， 

f[i][j]为 A的[0,i] 和B的[0,j]的LCS是多少

转移方程为 如果不等 max(f[i][j-1], f[i-1][j]), 如果相等， f[i-1][j-1]+1,其实这里有点贪婪的感觉，所以我觉得

max(f[i-1][j-1]）不等的时候和max(f[i-1][j-1]+1)反倒更明白些，速度话说快了一点点。。哈哈哈

再就是我做DP的和string相关的题目的时候总是犯一个低级错误，因为需要考虑空string的情况，dp 的函数总是多开一位，但是遍历string的时候就需要记得减掉一位，每次都犯错。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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(); 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++){ f[i][j]=max(f[i-1][j], f[i][j-1]); f[i][j]=max(f[i][j],A[i-1]==B[j-1]? f[i-1][j-1]+1: f[i-1][j-1]); } } return f[m][n]; } };