最长公共上升子序列的DP解法及其优化

定义状态

Fi 表示以 a 串的前 i 个整数与 b 串的前 j 个整数且以 b[j] 为结尾构成的 LCIS 的长度。

状态转移方程:

①Fi = Fi-1 (a[i] != b[j])

②Fi = max(Fi-1+1) (1 <= k <= j-1 && b[j] > b[k])

现在我们来说为什么会是这样的状态转移方程呢?

对于①,因为 Fi 是以 b[j]为结尾的 LCIS,如果 Fi>0 那么就说明 a[1]..a[i]中必然有一个整数 a[k]等于 b[j], 因为 a[k]!=a[i],那么 a[i]对 Fi 没有贡献,于是我们不考虑它照样能得出 Fi 的最优值。所以在 a[i]!=b[j]的情况下必然有 Fi=Fi-1。

对于②,前提是 a[i] == b[j], 我们需要去找一个最长的且能让 b[j]接在其末尾的 LCIS。之前最长的 LCIS 在哪呢?首先我们要去找的 F 数组的第一维必然是 i -1。因为 i 已经拿去和 b[j]配对去了,不能用了。并且也不能是 i -2,因为 i - 1 必然比 i - 2 更优。第二维呢?那就需要枚举 b[1]...b[j-1]了,因为你不知道这里面哪个最长且哪个小于 b[j]。这里还有一个问题,可不可能不配对呢?也就是在 a[i]==b[j]的情况下,需不需要考虑 Fi=Fi- 1 的决策呢?答案是不需要。因为如果 b[j]不和 a[i]配对,那就是和之前的 a[1]...a[j-1]配对(假设 Fi-1>0,等于 0 不考虑),这样必然没有和 a[i]配对优越。(为什么必然呢?因为 b[j]和 a[i]配对之后的转移是 max(Fi-1)+1,而和之前的 i配对则是max(F[i-1][k])+1。


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1001;
int a[MAXN], b[MAXN];
int f[MAXN][MAXN];
int n, m;
void init(){
    memset(f, 0, sizeof(f));
}
//核心代码
void dp(){
    init();
    int i, j, k;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            f[i][j] = f[i-1][j]; // if(a[i] != b[j])
            if(a[i] == b[j]){
                int MAX = 0;
                for(k = 1; k <= j-1; k++) if(b[j] > b[k]) //枚举最大的f[i-1][k]{
                    MAX = max(MAX, f[i-1][k]);
                }
                f[i][j] = MAX+1;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; i++) ans = max(ans, f[n][i]);
    printf("%d\n", ans);
}

转自:wall_f