题目链接:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
给两个序列,找出最长公共子序列
运算时递归函数如下:
$$dp[i+1]=\begin{cases}0 & i==0 \ ||\ j==0\\dp[i][j]+1 & s[i]=p[j]\\max(dp[i][j+1],dp[i+1][j]) & s[i]!=p[j]\end{cases}$$
代码如下:
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int maxx=1010; int main (){ int dp[maxx][maxx]; string s,p; int q; cin>>q; while(q--){ cin>>s>>p; int a=s.size(),b=p.size(); for(int i=1;i<=a;i++) dp[i][0]=0; for(int i=1;i<=b;i++) dp[0][i]=0; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ if(s[i]==p[j]) dp[i+1][j+1]=dp[i][j]+1; else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); } } cout<<dp[a][b]<<endl; } return 0; }
错点:
1.要先把i==0 || j==0的情况写好,如果直接在后面写,调用的时候可能出现调用没有赋值的量。
2.注意下标要从1开始,0要保留出来。
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。