hdu 1159 Common Subsequence (dp)

点击打开链接

题目意思：

简单DP应用。。

给你两个字符串看看有依次有多少字符相同，

Dp【i】【j】表示str_1的前i个字符与str_2的前J个字符有dp[i][j]个相同的。

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

#include"stdio.h" #include"string.h" #define N 1001 int dp[N][N]; int MAX(int a,int b) {if(a>b)return a;return b; } int main() {int len_1,len_2,i,j;char str_1[N],str_2[N];while(scanf("%s %s",str_1,str_2)!=-1){len_1=strlen(str_1);len_2=strlen(str_2);memset(dp,0,sizeof(dp));for(i=1;i<=len_1;i++){for(j=1;j<=len_2;j++)if(str_1[i-1]==str_2[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=MAX(dp[i-1][j],dp[i][j-1]);}printf("%d\n",dp[len_1][len_2]);}return 0; }

转载于:https://www.cnblogs.com/yyf573462811/archive/2012/10/28/6365159.html

总结

以上是生活随笔为你收集整理的hdu 1159 Common Subsequence (dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。