5101专题

#动态规划,线性动态规划#codevs 2185 CH 5101 LCIS 最长公共上升子序列

题目 求两个序列的最长公共上升子序列 分析 首先,优化的方法 for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i]==b[j])for (int k=0;k<j;k++)if (b[k]<a[i])f[i][j]=max(f[i][j],f[i-1][k]+1); 但是 O ( n 3 ) O(n^3) O(n3)的算法对于 n