关于算法竞赛进阶指南P267 LCIS 的问题

根据书中所言，朴素做法O(n^3)时转移方程的计算如下：

CPP

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 将

CPP

f[i][j]=f[i-1][j]

提至

CPP

if(b[k]<b[j])

之上，并不加判断条件却可以得出正确结果请问对于书中给出的代码是否需要做初始化以及初始化成什么亦或是书中给出代码存在逻辑上的漏洞萌新不解，求dalao解惑

关于算法竞赛进阶指南P267 LCIS 的问题

讨论操作

回复

相关推荐

关于算法竞赛进阶指南P267 LCIS 的问题