问题标题：
杭电acm1159,公共子序列问题,我的思路漏掉什么了啊?老是wronganswer网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）我的思路是这样的：读入两个字符串A、B对A的每一
问题描述：
杭电acm1159,公共子序列问题,我的思路漏掉什么了啊?老是wronganswer
网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）
我的思路是这样的：
读入两个字符串A、B
对A的每一个字符
在B里一个个字符匹配
匹配上的话
{公共子序列计数加1；记下B中这个位置,下次就从此处开始匹配；}
然后返回计数值（这就是以A为基准的公共子序列的长度）
然后把A、B位置调换,再做一遍以上过程,得到另一个计数值（以B为基准的）
将这两个值比较,较大的就是所求结果
我这样做测试用例都没问题,我又试了很多例子,也都对了,提交就是wronganswer,把数组扩大也不对,真不知哪里错了,
我的代码也搁这吧,可以结合着看一看
#include
usingnamespacestd;
intsub(chara[1000],charb[1000])
{
inti,j;
intcount=0,find=-1;
for(i=0;a[i]!='';i++)
for(j=find+1;b[j]!='';j++)
{
if(a[i]==b[j])
{
count++;
find=j;
break;
}
}
returncount;
}
intmain()
{
chara[1000],b[1000];
while(cin>>a>>b)
{
intx=sub(a,b),y=sub(b,a);
cout
陈旭武回答：
楼主的思路错了,你的代码我就不看了.
就是动态规划.
辅助空间变化示意图.
abcfbc
a111111
b122222
f122333
c123334
a123334
b123344
子结构特征：
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
#include
#definemax(a,b)a>b?a:b
intf[500][500];
intmain()
{
chara[500],b[500];
inti,j;
intlena,lenb;
while(scanf("%s%s",a,b)!=EOF)
{
lena=strlen(a);
lenb=strlen(b);
for(i=0;i
