最长公共子序列<DP>

xiaoxiao2021-02-27  293

dp[i][j]表示s1序列到i个字符,s2序列到j个字符的最长公共子序列有长。

for i=1 to l1 

for j=1 to l2 

if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]         Q1为什么不能是dp[i-1][j]    dp[i][j-1]

else

dp[i][j]=max(dp[i-1][j],dp[i][j-1]

Q1因为dp[i-1][j]会有可能前面那个s1的i-1与i相同,然后j已经在i-1的时候计算过了一次,i再计算就重复了。

因为dp[i][j-1]的话,可能s1[i]只有一个,可是j-1的已经计算过了一次s1[i],再计算也就重复了。

如果不相等,那么dp[i][j]=max(dp[i-1][j],dp[i][j-1])是为了确定dp[i][j]为s1到第i个,s2到第j个的最大,i>i-1&&j-1

#include<iostream> #include <stdio.h> #include <string.h> #include <set> #include <vector> #include <stdlib.h> #include<direct.h> #include <io.h> #include <direct.h> using namespace std; int dp[500][500]; char s1[500]; char s2[500]; int main(){ freopen("in.txt","r",stdin); int i,j,k,f1,f2,f3,t1,t2,t3,n,m,T,t; cin >> s1 >> s2; int l1=strlen(s1); int l2=strlen(s2); memset(dp,0,sizeof(dp)); for(i=1;i<=l1;i++) for(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][j-1],dp[i-1][j]); } cout << dp[l1][l2] << endl; return 0; }

转载请注明原文地址: https://www.6miu.com/read-2140.html

最新回复(0)