Question

杭电acm 1159，公共子序列问题，我的思路漏掉什么了啊？老是wrong answer

网上有人说是动态规划，我怎么没看出来呢……（新手，对该算法还不太懂）
我的思路是这样的：
读入两个字符串A、B
对A的每一个字符
在B里一个个字符匹配
匹配上的话
{公共子序列计数加1；记下B中这个位置，下次就从此处开始匹配；}
然后返回计数值（这就是以A为基准的公共子序列的长度）
然后把A、B位置调换，再做一遍以上过程，得到另一个计数值（以B为基准的）
将这两个值比较，较大的就是所求结果

我这样做测试用例都没问题，我又试了很多例子，也都对了，提交就是wrong answer,把数组扩大也不对，真不知哪里错了，请高手指点！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1159

我的代码也搁这吧，可以结合着看一看
#include<iostream>
using namespace std;
int sub(char a[1000],char b[1000])
{
int i,j;
int count = 0,find = -1;
for(i=0;a[i]!='\0';i++)
for(j=find+1;b[j]!='\0';j++)
{
if(a[i] == b[j])
{
count ++;
find = j;
break;
}
}
return count;
}
int main()
{
char a[1000],b[1000];
while(cin>>a>>b)
{
int x=sub(a,b),y=sub(b,a);
cout<<((x>y)? x:y)<<endl;
}
return 0;
}

Answer 1

楼主的思路错了，你的代码我就不看了。。
就是动态规划。。
辅助空间变化示意图。。
a b c f b c
a 1 1 1 1 1 1
b 1 2 2 2 2 2
f 1 2 2 3 3 3
c 1 2 3 3 3 4
a 1 2 3 3 3 4
b 1 2 3 3 4 4

子结构特征：

f(i,j)= 1. f(i-1,j-1)+1 (a[i]==b[j])
或者2. max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])
由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有关, 而在计算f(i,j)时, 只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了, 这样就可以计算出f(i,j). 这样一直推到f(len(a),len(b))就得到所要求的解了.
我的AC代码。。。

#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int f[500][500];
int main()
{
char a[500],b[500];
int i,j;
int lena,lenb;
while(scanf("%s %s",a,b)!=EOF)
{
lena=strlen(a);
lenb=strlen(b);
for(i=0;i<=lena;i++)
{
f[i][0]=0;
f[0][i]=0;
}

for(i=1;i<=lena;i++)
for(j=1;j<=lenb;j++)
{
if(a[i-1]==b[j-1])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
printf("%d\n",f[lena][lenb]);
}
return 0;
}

参考资料。。
http://acm.hdu.edu.cn/forum/read.php?tid=3133
杭电LCY老师的动态规划课件。。
这题是里面的一道例题。。
楼主自己去看看吧。。
申请个论坛号就可以免费下载了。。