【DP复习4—LCS】HDU1159——Common Subsequence
题目：点击打开链接
没什么多说的，LCS问题盲打过，但我CE了两次，因为把I和J搞混了。。另外注意LCS是中间可以有间隔的，KMP则没有。另外别忘了前两天博客中曾经提到的二分法。
#include <iostream>#include <cstring>#include <string>using namespace std;int max(int a,int b){return a>b?a:b;}int dp[3400][3400];int main(){string a,b;while(cin>>a>>b){int as=a.size();int bs=b.size();for(int i=0;i<as;i++){for(int j=0;j<bs;j++){dp[i][j]=0;}}//dp[0][0]=1;for(int i=0;i<=as;i++){for(int j=0;j<=bs;j++){if(a[i]==b[j]){dp[i+1][j+1]=dp[i][j]+1;}else{dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);}}}cout<<dp[as][bs]<<endl;}return 0;}