两个序列 1.两个序列的最长公共子串(连续) 状态:f[i][j]表示a[i]与b[j]结尾的最长…… 转移: if(a[i]==b[j]) f[i][j] = f[i-1][j-1]+1 else f[i][j] = 0; 边界：0 答案：max (f[][]) 时间：O(n*m)

2.两个序列的最长公共子序列 状态:f[i][j]表示a[1---i],b[1---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]); 边界：0 答案：f[n][m] 时间：O(n*m)

3.三个序列的最长公共子序列 状态:f[i][j][k]表示a[1---i],b[1---j],c[1----k] 的最长…… 转移: if(a[i]==b[j] && b[j]==c[k]) f[i][j][k] = f[i-1][j-1][k-1] + 1 else f[i][j][k] = max(f[i-1][j][k],f[i][j-1][k], f[i][j][k-1]) 边界：0 答案：f[n][m][w] 时间：O(nmw)

4.两个序列的最长上升公共子序列（最长上升子序列+最长公共子序列） // 最长上升子序列：f[i]表示以a[i]结尾的最长上升子序列的长度

状态：f[i][j] 表示a[1---i]及b[1---j]的最长上升公共子序列的长度，b[j] 为结尾 代码： b[j] 为结尾的写法 for(int i=1; i<=n; i++){ mf = 0; for(int j=1; j<=m; j++){ if(b[j]< a[i]){ mf = max(mf,f[i-1][j]);//前缀最大的f[i-1]k],b[k]<a[i] } if(a[i] == b[j]) f[i][j] = mf + 1; else f[i][j] = f[i-1][j]; } }

代码： a[i] 为结尾的写法 for(j){ for(i) }

边界：f[i][0] = f[0][i] = 0 答案：ans = max(f[i][j])