作业帮杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）我的思路是这样的：读入两个字符串A、B对A的每一
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 04:55:47
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）我的思路是这样的：读入两个字符串A、B对A的每一
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer
网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）
我的思路是这样的：
读入两个字符串A、B
对A的每一个字符
在B里一个个字符匹配
匹配上的话
{公共子序列计数加1；记下B中这个位置,下次就从此处开始匹配；}
然后返回计数值（这就是以A为基准的公共子序列的长度）
然后把A、B位置调换,再做一遍以上过程,得到另一个计数值（以B为基准的）
将这两个值比较,较大的就是所求结果
我这样做测试用例都没问题,我又试了很多例子,也都对了,提交就是wrong answer,把数组扩大也不对,真不知哪里错了,
我的代码也搁这吧,可以结合着看一看
#include
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
杭电acm 1159,公共子序列问题,我的思路漏掉什么了啊?老是wrong answer网上有人说是动态规划,我怎么没看出来呢……（新手,对该算法还不太懂）我的思路是这样的：读入两个字符串A、B对A的每一
楼主的思路错了,你的代码我就不看了.
就是动态规划.
辅助空间变化示意图.
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
#include
#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