HDU1159（最长公共子序列+动态规划）

 最长公共子序列问题：（LCS）

1.string类的函数length()返回对象中字符的个数

2.假设string str;那么str中第i个字符应该是str[i-1]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1005;
int dp[maxn][maxn];
string str1;
string str2;
int lenth1,lenth2;
void lcs()
{memset(dp,0,sizeof(dp));lenth1=str1.length();//length返回string中字符的个数lenth2=str2.length();for(int i=0; i<=lenth1; i++)for(int j=0; j<=lenth2; j++){if(i==0||j==0)dp[i][j]=0;else if(str1[i-1]==str2[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}
}
int main()
{while(cin>>str1>>str2){lcs();printf("%d\n",dp[lenth1][lenth2]);}return 0;
}