Coincidence__牛客网

面试官行行好

#include<iosteream>
#include<cstring>
using namespace std;

int c[105][105];//用于存储动态转移方程

int main()
{
    string str1,str2;
    cin>>str1>>str2;
    int len1=str1.length(),len2=str2.length();
    memset(c,0,sizeof(c));//初始化动态转移方程
    /*核心部分*/
    for(int i=1;i<=len1;i++)
    {
         for(int j=1;j<=len2;j++)
          {
                if(str1[i-1]==str2[j-1])
                {
                     c[i][j]=max(c[i][j],c[i-1][j-1]+1);
                 }
                else
                {
                    c[i][j]=max(c[i-1][j],c[i][j-1]);
                }   
           }
    }
    /*****************/
    cout<<c[len1][len2]<<endl;
    return 0;
}

代码如上

原理如下

通过打表，记录每个表项c[i][j]表示str1中的第i个元素即str1[i]与str2中的第j个元素即str2[j]是否相等 ,简单来说：如果横竖（i,j）对应的两个元素相等，该格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。

编辑于 2019-03-11 21:18:51 回复(2)

吕劲昕

//LCS最长公共子序列
//动态规划 

//dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列
//假设str1第i位=str2第j位,那么此时的最长公共子序列等于dp[i-1][j-1]+1
//如果不相等,那么最长公共子序列等于dp[i][j-1]、dp[i-1][j]中的较大值
//要注意的是我们比较的是第i位和第j位的值，所以是str1[i-1] str2[j-1] 
//时间复杂度为O（len1*len2*1） 
#include<stdio.h>
#include<string.h>
int max(int x,int b){
	if(x>b) return x;
	return b;
}
int main(){
	char str1[101];
	char str2[101];
	int dp[101][101];
	while(scanf("%s %s",str1,str2)!=EOF){
		int len1=strlen(str1);
		int len2=strlen(str2);
		for(int i=0;i<=len1;i++){
			dp[i][0]=0;
		}
		for(int j=0;j<=len2;j++){
			dp[0][j]=0;
		}
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
				if(str1[i-1]==str2[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[len1][len2]); 
	}
}

发表于 2020-07-29 11:06:25 回复(0)

C++

之一不之

#include<bits/stdc++.h>
using namespace std;

int dp[100][100];//dp[i][j]表示str1中以i为末尾的字符串和str2中以j为末尾的字符串的公共子串长度

char str1[100];
char str2[100];

int main(){
    while(scanf("%s%s",str1+1,str2+1)!=EOF){//从下标1的位置开始输入，有利于后续边界条件的处理
        int n=strlen(str1+1);//求字符串长度
        int m=strlen(str2+1);
        for(int i=0;i<=n;i++){//带等号，因为从下标1开始输入
            for(int j=0;j<=m;j++){
                if(i==0||j==0){//边界条件处理，str1或者str2其中一个字符串为空串，则他们的公共子串长度为0
                    dp[i][j]=0;
                    continue;
                }        
                                //dp[i][j]分为两种情况，1--str1[i]和str2[j]相等，2--str1[i]和str2[j]不等
                if(str1[i]==str2[j]){    //当str1[i]和str2[j]相等了，表示当前这两个子串末尾字符相同，则dp转化为str1的上个字符和str2的上个字符求公共子串长度+1
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);  //当str1[i]和str2[j]不相等
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
    
    return 0;
}

发表于 2021-09-01 21:25:47 回复(0)

s_paul

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>

using namespace std;
const int MAXN = 101;
int dp[MAXN][MAXN];
int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        //int len1 = strlen(str1);
        //int len2 = strlen(str2);
        int len1 = str1.size();
        int len2 = str2.size();
        for(int i=0; i<=len1; ++i)
        {
            dp[i][0] = 0;
        }
        for(int j=0; j<=len2; ++j)
        {
            dp[0][j] = 0;
        }
        for(int i=1; i<=len1; i++)//i和j的初始值应该为1
        {
            for(int j=1; j<=len2; j++)
            {
                if(str1[i-1] == str2[j-1])//str数组里面相较于dp要全部前移一个
                {
                    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[len1][len2]);
    }
    return 0;
}

最长公共子序列的裸题，注意dp数组和str数组相差1即可

发表于 2021-05-13 17:22:04 回复(0)

用户抉择

#include <stdio.h>
#include <string.h>
int main()
{
    char a[101],b[101];
    int len1,len2,i,j;
    while(scanf("%s %s",a+1,b+1)!=EOF)
    {
        len1=strlen(a+1);
        len2=strlen(b+1);
        int dp[len1+1][len2+1];
        for(i=0;i<=len1;i++)
        {
            for(j=0;j<=len2;j++)
            {
                if(i==0||j==0) 
                    dp[i][j]=0;
                else if(a[i]==b[j])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
            }
        }
        printf("%d\n",dp[len1][len2]);
    }
    return 0;
}

发表于 2021-03-27 22:43:11 回复(1)

C/C++

胡桃夹子🎈

典型动态规划

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string str1, str2;
    while (cin>>str1>>str2)
    {
        int n = str1.size() + 1, m = str2.size() + 1;
        int** dp = new int* [n];
        for (int i = 0; i < n; i++)
        {
            dp[i] = new int[m];
            for (int j = 0; j < m; j++)
            {
                if (i == 0 || j == 0)
                {
                    dp[i][j] = 0;
                    continue;
                }
                if (str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        cout << dp[n - 1][m - 1] << endl;
        for (int k = 0; k < n; k++)
            delete[] dp[k];
        delete[] dp;
    }
    return 0;
}

发表于 2020-07-10 09:45:46 回复(0)

找到好工作！！！

#include<stdio.h>
#include<string.h>
int max(int a,int b){
 return a>b?a:b;
}
int main(){
 char s1[110],s2[110];
 int dp[110][110];
 while(~scanf("%s%s",s1,s2)){
  int l1=strlen(s1);
  int l2=strlen(s2);
  for(int i=0;i<=l1;i++)
   dp[i][0]=0;
  for(int j=0;j<=l2;j++)
   dp[0][j]=0;
  for(int i=1;i<=l1;i++){
   for(int j=1;j<=l2;j++){
    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[l1][l2]);
 }
 return 0;
}

发表于 2019-02-18 09:17:10 回复(0)

Python

TimeMac

while True:
    try:
        string1,string2 = input(),input()
        result = [[0 for i in range(len(string2)+1)] for j in range(len(string1)+1)]
        #result[i][j]保存string1前i个子串和string2前j个子串的公共子序列
        for i in range(1,len(string1)+1):
            for j in range(1,len(string2)+1):
                result[i][j] = max(result[i-1][j],result[i][j-1])
                if string1[i-1]==string2[j-1]:
                    result[i][j] = result[i-1][j-1]+1    #等于子串都减一的公共子序列长度加一
        print(result[-1][-1])
    except Exception:
        break

编辑于 2018-10-12 09:29:32 回复(0)

牛客7464386号

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[101][101];
char a[102];char b[102];
int main(){
    while(scanf("%s%s",a+1,b+1)!=EOF){
        int len1=strlen(a+1);
        int len2=strlen(b+1);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;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]);
            }
        printf("%d\n",dp[len1][len2]);
    }
}

发表于 2018-02-21 12:10:16 回复(0)

Benson666

注意String类的下标

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String a = in.next();
            String b = in.next();
            int m = a.length();
            int n = b.length();
            int[][] dp = new int[m+1][n+1];
            for(int i=0;i<n+1;i++){
                dp[0][i] = 0;
            }
            for(int i=0;i<m+1;i++)
                dp[i][0] = 0;
            
            for(int i=1;i<m+1;i++){
                for(int j=1;j<n+1;j++){
                    if(a.charAt(i-1) == b.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[m][n]);
            
        }
    }
}

发表于 2018-02-12 19:51:05 回复(0)

263保洁小妹

参考的书上的思路。要注意下标的含义，头脑要清醒

//最长公共子序列(LCS)问题，动态规划问题的一种，参考王道《机试指南》
#include <stdio.h>
#include <string.h>
#define N 101
//N是最大字符串长度
int dp[N][N];
/*dp[i][j]表示s1中前i个字符、s2中前j个字符组成的
两个字符串最长公共子序列长度*/
/*递推关系
dp[0][j]=0
dp[i][0]=0
dp[i][j]=dp[i-1][j-1]+1(如果s1[i-1]==s[j-1]的话)
dp[i][j]=max{dp[i-1][j], dp[i][j-1]}(如果s1[i-1]!=s[j-1]的话)
前面括号里下标要-1是因为字符串下标从0开始，s1第1个字符是s[0]
*/
int Max(int a, int b)//返回a、b之中的较大值
{
    return a>b? a: b;
}
int main()
{
    char s1[N], s2[N];
    while(gets(s1))
    {
        gets(s2);
        int len1=strlen(s1);
        int len2=strlen(s2);
        for(int i=0; i<N; i++)//先把dp数组清零
        {
            for(int j=0; j<N; j++)
            {
                dp[i][j]=0;
            }
        }
        for(int i=0; i<N; i++)//dp[i][0]=0，dp[0][j]=0
        {
            dp[i][0]=0;
            dp[0][i]=0;
        }
        for(int i=1; i<=len1; i++)
        {
            for(int j=1; j<=len2; j++)
            {
                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[len1][len2]);
    }
    return 0;
}

发表于 2018-02-28 15:56:59 回复(0)

liuhuiming

简单的动态规划还可以做一下的

#include <iostream>
#include<vector>
#include<string>
using namespace std;

int main() {
//求最长公共子序列，这是一道简单的动态规划的题目，用二维数组来完成，dp[i][j]的含义为
//字符串s1[0]-s1[i-1]形成的字符串与字符串s2[0]-s2[j-1]形成的字符串的最长公共子序列的值
string str1,str2;
cin>>str1>>str2;
int m=str1.size();
int n=str2.size();
vector<vector<int>>dp(m+1,vector<int>(n+1,0));//定义dp数组的容量和初值
//找到状态转移方程
for(int i=1;i<m+1;i++){
    for(int j=1;j<n+1;j++){
        //这里选择一行一行地进行填充
        if(str1[i-1]==str2[j-1])
        dp[i][j]=dp[i-1][j-1]+1;
        else{
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
}
cout<<dp[m][n]<<endl;
}

编辑于 2024-01-17 17:58:50 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

const int Max=100;
int dp[Max][Max];

int main() {
    char s1[Max];
    char s2[Max];
    while(cin>>s1+1>>s2+1) {
        int n=strlen(s1+1);
        int m=strlen(s2+1);
        int answer=0;
        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(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]);
                }
                answer=max(answer,dp[i][j]);
            }
        }
        cout<<answer<<endl;
    }
    return 0;
}

发表于 2022-10-16 15:44:39 回复(0)

爱吃姜烩葱

s1=input()
s2=input()
m,n=len(s1),len(s2)
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if s1[j-1]==s2[i-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[-1][-1])

经典dp，dp[i][j]表示s2的前i个字符与s1的前j个字符所拥有的最大公共子字符串的长度

编辑于 2024-03-28 20:11:10 回复(0)

9本2硕

#include <iostream>

using namespace std;

int dp[105][105];

int main() {

string a,b;

cin>>a>>b;

for(int i=1;i<=a.size();i++){

for(int j=1;j<=b.size();j++)

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]);

}

cout<<dp[a.size()][b.size()];

}

发表于 2024-03-21 11:14:12 回复(0)

ABan_

最难以接受的是...最长公共子序列，子串是不需要连续的..这个要注意

发表于 2024-03-16 16:08:23 回复(0)

会时Kk

哈哈哈哈哈

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s1,s2;

while(cin >> s1 >> s2){

vector<vector<int>> dp(s1.size()+1,vector<int> (s2.size()+1,0));

for(int i=1; i <=s1.size();++i){

for(int j=1; j <= s2.size();++j){

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]);

}

cout << dp[s1.size()][s2.size()];

}

// 64 位输出请用 printf("%lld")

发表于 2023-03-22 09:37:33 回复(0)

C++

Edward王

注意下标。这里为方便起见，从数组第二个位置(即下标为1开始存)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int main(){
    char s1[101];
    char s2[101];
    int dp[101][101]; //存s1[i]和s2[j]结尾的的公共子序列的长度
    while(scanf("%s %s",s1+1,s2+1) != EOF){ //从下标为1开始存
        int n = strlen(s1+1); //C字符数组长度用strlen()
        int m = strlen(s2+1);
        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(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]);
                }
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

发表于 2023-03-19 19:23:02 回复(0)

C++

lyw菌

//求最长公众子序列，比较经典的动态规划问题

#include "stdio.h"

#include "string"

using namespace std;

int main(){

char buf1[110],buf2[110];

int dp[110][110];//dp[i][j]表明第一个字符串的前i个字符，第二个字符串的前j个字符

while (scanf("%s",buf1) != EOF){

scanf("%s",buf2);

string str1 = buf1,str2 = buf2;

for (int i = 0; i <= str1.size(); ++i) {

for (int j = 0; j <= str2.size(); ++j) {

if (i == 0 || j == 0)

dp[i][j] = 0;

else{

if (buf1[i-1] == buf2[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[str1.size()][str2.size()]);

}

发表于 2023-03-16 10:10:12 回复(0)

C

乔楚

//用一个二维数组dp[i][j],表示p[0]~p1[j-1]与p2[0]~p2[i-1]的最长公共子序列长度

int max(int a,int b)

{

if(a>b)

return a;

else

return b;

}

int main()

{

char p1[100],p2[100];

int dp[101][101];

scanf("%s",p1);

scanf("%s",p2);

int len1,len2,i,j;

len1=strlen(p1);

len2=strlen(p2);

for(i=0;i<=len2;i++)

dp[i][0]=0;

for(i=0;i<=len1;i++)

dp[0][i]=0;

for(i=1;i<=len2;i++)

{

for(j=1;j<=len1;j++)

{

if(p1[j-1]==p2[i-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[len2][len1]);

return 0;

}

发表于 2023-03-02 22:59:09 回复(0)

Coincidence

输入描述:

输出描述:

输入

输出

典型动态规划

问题信息

热门推荐

通过挑战的用户

相关试题