第一行输入一个整数 n 和 m ，表示字符串 s1 和 s2 的长度。接下来第二行和第三行分别输入一个字符串 s1 和 s2。
输出两个字符串的最长公共子序列的长度
5 6 abcde bdcaaa
2
最长公共子序列为 "bc" 或 "bd" ，长度为2
3 3 abc xyz
0
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
string s1, s2;
cin >> s1 >> s2;
// 时间复杂度O(MN)，空间复杂度O(MN)
int dp[n + 1][m + 1];
for (int i = 0; i <= n; ++i) dp[i][0] = 0;
for (int j = 0; j <= m; ++j) dp[0][j] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = s1[i - 1] == s2[j - 1] ?
dp[i - 1][j - 1] + 1 :
max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[n][m];
return 0;
} 
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int dp[N][N]={0};
int n,m;
string a,b;
int main()
{
cin>>n>>m;
cin>>a>>b;
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]);
}
}
}
cout<<dp[n][m]<<endl;
return 0;
} n1,n2 = list(map(int,input().split())) s1 = input() s2 = input() def common(s1,s2): #dp[i][j]为s1[...i]和s2[...j]的最长公共子序列,这里包括索引i和j #dp[i][j]为s1到索引i,s2到索引j的最长公共子序列 n1 = len(s1) n2 = len(s2) dp = [[0]*(n2) for _ in range(n1)] if s1[0]==s2[0]: dp[0][0]=1 for i in range(n1): if s2[0] in s1[:i+1]: dp[i][0]=1 for j in range(n2): if s1[0] in s2[:j+1]: dp[0][j]=1 for i in range(1,n1): for j in range(1,n2): if s1[i]==s2[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[n1-1][n2-1] res = common(s1,s2) print(res)方法2：
n1,n2 = list(map(int,input().split())) s1 = input() s2 = input() def common(s1,s2): #dp[i][j]为s1[...i-1]和s2[...j-1]的最长公共子序列,这里包括索引i-1和j-1，不包括索引i和j,即s1[:i],s2[:j] #dp[i][j]为s1截至到第i个字符，s2截至到第j个字符的最长公共子序列 n1 = len(s1) n2 = len(s2) dp = [[0]*(n2+1) for _ in range(n1+1)] for i in range(1,n1+1): for j in range(1,n2+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]) return dp[n1][n2] res = common(s1,s2) print(res)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
in.nextLine();
String s1 = in.nextLine();
String s2 = in.nextLine();
int dp[][] = new int[n + 1][m + 1];
for(int i = 0;i <= n;i++){
for(int j = 0;j <= m;j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}else if(s1.charAt(i - 1) == s2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j]);
}
}
}
System.out.println(dp[n][m]);
}
} 
#include <iostream>
#include <vector>
using namespace std;
int main() {
string s1,s2;
int n,m;
cin >> n >> m;
cin >> s1 >> s2;
if (s1.size() > s2.size()) {
swap(n, m);
swap(s1,s2);
}
vector<int> f(m+1,0);
int res = 0;
for (auto i=1; i<=n; i++) {
auto left_up=0,last=0;
for (auto j=1; j<=m; j++) {
auto tmp = left_up;
left_up = f[j];
if (s1[i-1] == s2[j-1]) {
// f[i][j] = f[i-1][j-1] + 1;
f[j] = tmp + 1;
}
else {
// f[i][j] = max(f[i-1][j],f[i][j-1]);
f[j] = max(f[j], last);
}
last = f[j];
res = max(res,f[j]);
}
}
cout << res << endl;
}
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n,m;
string s1, s2; // s1的长度n < s2的长度m
cin>>n>>m;
if(n>m){
cin>>s1>>s2;
}else{
int temp = n;
n = m;
m = temp;
cin>>s2>>s1;
}
vector<int> pre(n+1,0);
vector<int> cur(n+1, 0);
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s1[j-1]==s2[i-1]){
cur[j] = pre[j-1]+1;
}else{
cur[j] = max(cur[j-1], pre[j]);
}
}
pre = cur;
}
cout<<pre[n];
return 0;
}
n,m = list(map(int,input().split())) s1=input() s2=input() shorterLength = min(n,m) longerLength = max(n,m) # 空间复杂度O(mn) # dp = [[0]*(longerLength+1) for i in range(shorterLength+1)] # if shorterLength==m: # s1,s2 = s2,s1 # for i in range(1,shorterLength+1): # for j in range(1,longerLength+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]) # print(dp[shorterLength][longerLength]) # 空间复杂度O(min(m,n)) dp1 = [0]*(shorterLength+1) dp2 = [0]*(shorterLength+1) if shorterLength==m: s1,s2 = s2,s1 for i in range(1,longerLength+1): for j in range(1,shorterLength+1): if s2[i-1]==s1[j-1]: dp2[j]=dp1[j-1]+1 else: dp2[j]=max(dp2[j-1],dp1[j]) dp1 = dp2.copy() print(dp2[shorterLength])
#include <iostream>
#include <vector>
//using namespace std;
int longestCommonSubsequence(const std::string& str1,const std::string&str2)
{
int m=str1.size(),n=str2.size();
std::vector<std::vector<int>> dp(m+1,std::vector<int>(n+1, 0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(str1[i-1]==str2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
{
dp[i][j]=std::max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}
int main() {
int a, b;
while (std::cin >> a >> b) // 注意 while 处理多个 case
{
std::string str1, str2;
std::cin >> str1 >> str2;
std::cout << longestCommonSubsequence(str1, str2) << std::endl;
}
} 
#include <cstdio>
#include <iostream>
using namespace std;
int dp[1001][1001];
int main(){
int n,m;
scanf("%d%d",&n,&m);
char s1[n];
char s2[m];
scanf("%s%s",s1,s2);
for(int i = 0; i <= n; ++i){ //前多少个，0~n 共n+1个
for(int j = 0; j <= m; ++j){ //前多少个，0~m 共m+1个
if(i==0 || j==0){
dp[i][j] = 0;
continue;
}
//核心4句
if(s1[i-1] == s2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{ //if(s1[i-1] != s2[j-1])
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
printf("%d\n",dp[n][m]);
return 0;
} import sys i = 0 m = n = 0 s1 = s2 = "" for line in sys.stdin: a = line.split() if i == 0: m, n = int(a[0]), int(a[1]) elif i == 1: s1 = a[0] else: s2 = a[0] i += 1 dp = [[0 for _ in range(n+1)] for _ in range(m+1)] for i in range(m): for j in range(n): if s1[i] == s2[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]) print(dp[m][n])
#include "cstdio"
#include "string"
#include "iostream"
using namespace std;
int DP[1001][1001];
int main(){
int m,n;
scanf("%d%d",&n,&m);
char a[1001];
char b[1001];
scanf("%s%s",a,b);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (i==0||j==0){
DP[i][j]=0;
continue;
}
if (a[i-1]==b[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",DP[n][m]);
} 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include "cstdio"
using namespace std;
/// 集合 : a的前i 个字母,b的前j个字母 中所有公共子序列
/// 属性: 长度最大值 max
/// 状态 转移: 00 01 10 11 , 代表 a的第i 个字母,b的第j个字母包含不包含在公共子序列中
/// 00: f[i-1][j-1] 01 10 不好表示 ,可以用 包含这两个的集合来算 ,因为 f[i][j] 包含 f[i-1][j] 包含 01 , 以此类推10 , 求 max 可以有重复 ,只要不漏掉状态就可以,因为多个重复取最大值 仍然不变
/// 且 00 的f[i-1][j-1] 也可以省略 ,因为 f[i-1][j-1] 包含在 f[i][j-1] 和 f[i-1][j] 当中
const int N=1010;
int n,m;
int f[N][N];
char s1[N],s2[N];
int main() {
cin >> n >> m;
scanf("%s%s",s1+1,s2+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(s1[i] == s2[j])
f[i][j] = max (f[i][j] , f[i-1][j-1]+1);
}
}
cout <<f[n][m]<< endl;
return 0;
}
// 64 位输出请用 printf("%lld") 
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
let [n,m]=(await readline()).split(" ").map(it=>parseInt(it));
let s1=await readline();
let s2=await readline();
let mat=new Array(n+1).fill(0).map(()=>new Array(m+1).fill(0));
for(let i=0;i<n;i++){
for(let j=0;j<m;j++){
if(s1[i]==s2[j]){
mat[i+1][j+1]=mat[i][j]+1;
}else{
mat[i+1][j+1]=Math.max(mat[i+1][j],mat[i][j+1]);
}
}
}
console.log(mat[n][m]);
}()
m,n = list(map(int,input().split())) s = input() t = input() def solution(s,t): m = len(s) n = len(t) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): if s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i][j-1],dp[i-1][j]) return dp[m][n] res = solution(s,t) print(res)
#首先读入数据
n,m = map(int,input().split(' '))
s1 = input()
s2 = input()
#然后构造一个dp表,构造dp表的时候注意n,m 的位置
dp = [[0 for i in range(m+1)] for j in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+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])
print(dp[n][m]) import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
char[] s1;
char[] s2;
int[][] dp;
s1 = sc.next().toCharArray();
s2 = sc.next().toCharArray();
int ans = 0;
dp = new int[n + 1][m + 1];
// 每个dp[i][j]代表s1以第i个字母结尾，s2以第j个字母结尾时的最长公共子序列数
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m ; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
continue;
}
// 先假设不相同，则不添加到最长公共子序列中
// 因此比较s1以第i-1个字母结尾，s2以第j个字母结尾
// 和s1以第i个字母结尾，s2以第j-1个字母结尾两个谁更大
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
// 如果相同，则可以添加到最长公共子序列中
// 因此比较未到达该位置的dp[i - 1][j - 1]+1后和到达该位置的dp[i][j]谁大
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
// dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + 1);
// dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - 1] + 1);
}
ans = Math.max(ans, dp[i][j]);
}
}
System.out.println(ans);
}
} #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
string s1;
string s2;
cin>>s1;
cin>>s2;
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(s1[i]==s2[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]);
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
import sys def longnums(str1): if(len(str1) != 0): nums1 = str1[1] nums2 = str1[0] len1 = len(nums1) len2 = len(nums2) dp = [[0 for col in range(len2+1)] for row in range(len1+1)] for i in range(1,len1+1): for j in range(1,len2+1): if(nums1[i-1] == nums2[j-1]): dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i][j-1],dp[i-1][j]) return dp[len1][len2] str1 = [] for line in sys.stdin: a = line.split() str1 = a + str1 print(longnums(str1))
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution{
public:
int dp(string s1,string s2){
//s1是短串
vector<int >dp(s1.size()+1,0);
//dp数组
vector<int >res(s1.size()+1,0);
//保存上轮dp的结果，当前比较位相等时用来对上一位的最大值+1
for(int i = 1 ; i <= s2.size();i++){
for(int j = 1;j <= s1.size();j++){
//相等时判断上一轮dp上一位的最长序列长
if(s2[i-1] == s1[j-1]) dp[j] = res[j-1]+1;
//因为不相等时，可以取当轮dp的最大值，也可是上一轮的本位置dp值
else dp[j] = max(dp[j-1],res[j]);
}
//开始下一位的dp时，更新上一轮的dp值进res
for(int j = 1;j <= s1.size();j++) res[j] = dp[j];
}
return dp[s1.size()];
}
};
int main(){
int n,m;
while(cin>>n>>m){
string s1,s2;
cin>>s1>>s2;
if(s1.size() > s2.size()) swap(s1, s2);
//保证s1为短串，dp方法正常进行
Solution solo;
cout<<solo.dp(s1,s2)<<endl;
}
return 0;
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
