此题经典线性动态规划.
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int maxn=505;
- int d[maxn][maxn];
- int main(void){
- string a,b;
- while(cin>>a>>b){
- memset(d,0,sizeof(d));
- for(int i=1;i<=a.length();i++){
- for(int j=1;j<=b.length();j++){
- if(a[i-1]==b[j-1]){
- d[i][j]=d[i-1][j-1]+1;
- }
- else{
- d[i][j]=max(d[i][j-1],d[i-1][j]);
- }
- }
- }
- cout<<d[a.length()][b.length()]<<endl;
- }
- return 0;
- }
- POJ-1458 LCS(线性动态规划)
来源: http://www.bubuko.com/infodetail-2554045.html