12_7最长公共子序列

给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A="1A2C3D4B56”，B="B1D23CA45B6A”，”123456"或者"12C4B6"都是最长公共子序列。

给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例：
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6

自己写的，边界条件写的不够优美

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        if(0 == n || 0 == m){
            return 0;
        }
        vector< vector<int> > dp(n, vector<int>(m, 0));
        for(int i=0; i<n; ++i){
            if(A[i] == B[0]){
                for(int k=i; k<n; ++k){
                    dp[k][0] = 1;
                }
                break;
            }
        }
        for(int j=0; j<m; ++j){
            if(A[0] == B[j]){
                for(int k=j; k<m; ++k){
                    dp[0][k] = 1;
                }
                break;
            }
        }
        for(int i=1; i<n; ++i){
            for(int j=1; j<m; ++j){
                if(A[i] == B[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n-1][m-1];
    }
};

参考答案，写的优美

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        if(0 == n || 0 == m){
            return 0;
        }
        vector< vector<int> > dp(n+1, vector<int>(m+1, 0));
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                if(A[i] == B[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        return dp[n][m];
    }
};