dp[i][j]是两个字符串长度为i j的值。
const int N = 1010;
class Solution {
public:
int dp[N][N];
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(text1[i-1] == text2[j-1]) {
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][m];
}
};
dp[i][j]为字符串下标为i,j的值
const int N = 1010;
class Solution {
public:
int dp[N][N];
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
dp[0][0] = text1[0] == text2[0] ? 1 : 0;
for(int i = 1; i < n; i++){
dp[0][i] = text1[0] == text2[i] ? 1 : dp[0][i-1];
dp[i][0] = text1[i] == text2[0] ? 1 : dp[i-1][0];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
if(text1[i] == text2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1]));
}
}
}
return dp[n-1][m-1];
}
};