给定两个字符串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];
}
};
