求最长公共子序列的长度

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

解题思路：

设一个C[i,j]: 保存A_i与B_j的LCS的长度。

1.首先利用一个二维数组C[i-1][j-1]来记录A串中前i-1个数和B串中的前j-1个数的最大公共子序列长度。

2.然后当我们开始挑选A，B串的下一个时即确定C[i][j]时，如果这两个相等，即A[i-1] == B[j-1]，那么就可以直接把这相等的字母加进去，即C[i][j] = C[i-1][j-1] + 1.

3.当我们开始挑选A，B串的下一个时即确定C[i][j]时，如果这两个不相等，即A[i-1] ！=  B[j-1]，那么最大公共子列长度是C[i-1][j]和C[i][j-1]这两者较大值

递推方程为：

代码如下：

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        if(n == 0 || m == 0)
            return 0;
        
        vector<vector<int>> C(n+1,vector<int>(m+1));
        
        for(int i = 1; i <= n ; i++)
            {
            for( int j = 1; j <= m; j++)
                if(A[i-1] == B[j-1])
                    C[i][j] = C[i-1][j-1] + 1;
            else
                C[i][j] = (C[i-1][j] >= C[i][j-1] ? C[i-1][j] : C[i][j-1]);
            
        }
        
        return  C[n][m];
        
    }
};