最长公共上升子序列的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

本文链接:https://kaispace.com.cn/index.php/archives/355/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者