首页 > 代码库 > hdu 1159 Common Subsequence（最长公共子序列，DP）
hdu 1159 Common Subsequence（最长公共子序列，DP）
题意：
两个字符串，判断最长公共子序列的长度。
思路：
直接看代码，，注意边界处理
代码：
char s1[505], s2[505];int dp[505][505];int main(){ while(scanf("%s%s",s1,s2)!=EOF){ int l1=strlen(s1); int l2=strlen(s2); mem(dp,0); dp[0][0]=((s1[0]==s2[0])?1:0); rep(i,1,l1-1) if(s1[i]==s2[0]) dp[i][0]=1; else dp[i][0]=dp[i-1][0]; rep(i,1,l2-1) if(s1[0]==s2[i]) dp[0][i]=1; else dp[0][i]=dp[0][i-1]; rep(i,1,l1-1){ rep(j,1,l2-1){ if(s1[i]==s2[j]){ dp[i][j]=max( dp[i-1][j-1]+1,dp[i-1][j] ); dp[i][j]=max( dp[i][j],dp[i][j-1] ); }else{ dp[i][j]=max( dp[i-1][j],dp[i][j-1] ); } } } printf("%d\n",dp[l1-1][l2-1]); } return 0;}
hdu 1159 Common Subsequence（最长公共子序列，DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。