HDU--1159题Common Subsequence

动态规划问题，队友给说的这道题目，看完之后没有丝毫犹豫按照自己之前的理解就写出来了代码，根本就没有往动态规划上想。结果可想而知，wa了好几次都不知道为什么·······后来问了队友，才发现要用二维数组。

原题地址：点击打开链接。

题目大意就是给两个字符串，你要做的就是得出最长公共子序列。以abcfbc和abfcab为例，示意图：

仔细观察可以发现C[i][j]=C[i-1][j-1]+1; (a[i]==b[j]);

c[i][j]=max{c[i-1][j],c[i][j-1]} (a[i]!=b[i]);

所以我们只需考虑c[i-1][j-1],c[i-1][j],c[i][j-1];就可以求的所求的结果。

#include<stdio.h> #include<string.h> int c[1001][1001]; int main() { int i,j,max,len1,len2; char a[1001],b[1001]; while(scanf("%s %s",a,b)!=EOF) {len1=strlen(a); len2=strlen(b); memset(c,0,sizeof(c));//清零数组 for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(a[i-1]==b[j-1]) { c[i][j]=c[i-1][j-1]+1; }else c[i][j]=c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1]; } } printf("%d\n",c[len1][len2]); }return 0; }还有几天就要回去了，所以很多人和事我都要处理好，也只有夜深人静的时候我才能静下来学些东西。我真的不忍心看到身边的人那失望的表情，或许我这次离开，再次归来很多事情都变了吧。在离开前就静静的陪陪她们吧。