LCS 最长公共子序列
- for(int i=1; i<=n; i++)
- for(int j=1; j<=m; j++)
- {
- if(a[i]==b[j])
- f[i][j]=f[i-1][j-1]+1;
- else
- f[i][j]=max(f[i-1][j],f[i][j-1]);
- }
LIS 最长上升子序列
- for(int i=2; i<=n; i++)
- for(int j=1; j<i; j++)
- {
- if(a[i]>a[j])
- f[i]=max(f[i],f[j]+1);
- ans=max(ans,f[i]);
- }
- // 例题: LCIS,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] < a[i])
- f[i][j] = max(f[i][j], f[i - 1][k] + 1);
- }
- else f[i][j] = f[i - 1][j];
- // 例题: LCIS,O(N^2)
- for (int i = 1; i <= n; i++)
- {
- // val 是决策集合 S(i,j) 中 f[i-1][k] 的最大值
- int val = 0;
- // j=1 时, 0 可以作为 k 的取值
- if (b[0] < a[i]) val = f[i - 1][0];
- for (int j = 1; j <= m; j++)
- {
- if (a[i] == b[j]) f[i][j] = val + 1;
- else f[i][j] = f[i - 1][j];
- // j 即将增大为 j+1, 检查 j 能否进入新的决策集合
- if (b[j] < a[i]) val = max(val, f[i - 1][j]);
- }
- }
来源: http://www.bubuko.com/infodetail-3027704.html