根据书中所言,朴素做法O(n^3)时转移方程的计算如下:
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i]==b[j])
for(int k=0;k<j;k++)
if(b[k]<b[j])
f[i][j]=max(f[i][j],f[i-1][k]+1);
else f[i][j]=f[i-1][j];
但如果面对以下数据:
4 4
2 2 1 3
2 1 2 3
则输出结果为1
但答案显然为2
将
f[i][j]=f[i-1][j]
提至
if(b[k]<b[j])
之上,并不加判断条件却可以得出正确结果
请问对于书中给出的代码是否需要做初始化以及初始化成什么
亦或是书中给出代码存在逻辑上的漏洞
萌新不解,求dalao解惑