思路:线性DP
动态表示的集合:所有在第一个序列的前i个出现,且在第二个序列的前j个字母出现的子序列的集合。
题目描述
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
c++代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
const int N = text1.size();
const int M = text2.size();
vector<vector<int>> f(N+1, vector<int>(M+1, 0));
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= M; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(text1[i-1] == text2[j-1]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
}
}
return f[N][M];
}
};
ACwing版本
https://www.acwing.com/problem/content/description/899/
ACM模式 c++代码
体会区别,char a, b都是从脚标1开始有字母的,力扣模式的text1和text2脚标是从0开始有字母的
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = max(f[i-1][j], f[i][j - 1]);
if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] +1);
}
printf("%d\n", f[n][m]);
return 0;
}
为什么这样也能过?