最长公共子序列(一)

最长公共子序列(一)

⭐️难度：较难
⭐️类型：动态规划

📖题目：题目链接
描述
给定两个字符串 s1 和 s2，长度为 n 和 m 。求两个字符串最长公共子序列的长度。
所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 “arcaea” 的子序列有 “ara” 、 “rcaa” 等。但 “car” 、 “aaae” 则不是它的子序列。
所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。

数据范围 :
1≤m,n≤1000
1≤m,n≤1000 。保证字符串中的字符只有小写字母。

输入描述：
第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。
接下来第二行和第三行分别输入一个字符串 s1 和 s2。
输出描述：
输出两个字符串的最长公共子序列的长度
示例1
输入：

5 6
abcde
bdcaaa

输出：

2

说明：

最长公共子序列为 “bc” 或 “bd” ，长度为2

示例2
输入：

3 3
abc
xyz

输出：

0

📚题解：

f(x,y)的公共子串长度依赖于f(x-1,y-1)

在这里插入代码片#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>#include<vector>// vector不需要.h#include<list>#include<set>// // 可以用 set 和 multiset#include<unordered_set>// 可以用 unordered_set 和 unordered_multiset#include<map>// 可以用 map 和 multimap#include<unordered_map>// 可以用 unordered_map 和 unordered_multimap#include<algorithm>#include<string>#include<iostream>#include<queue>#include<stack>usingnamespacestd;chars1[1005];chars2[1005];intdp[1005][1005]={0};// dp[i][j] s1的前i个元素 s2的前j个元素 的最大公共长度intmain(){intn,m;while(scanf("%d%d",&n,&m)!=EOF){scanf("%s%s",s1,s2);for(inti=1;i<=n;i++){dp[i][0]=0;// s2长度为0}for(inti=1;i<=m;i++){dp[0][i]=0;// s1长度为0}for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){// s1[0] ~ s1[i-1] 和 s2[0] ~ s2[j-1]if(s1[i-1]==s2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);// 前一步的最长公共子串长度}}}printf("%d\n",dp[n][m]);}return0;}