LCS、LIS、LICS算法

概念

首先，要理解子串和子序列的含义：

子串：来源于原序列连续的一段。
子序列：来源于原序列中元素相对顺序不变的一段，不要求元素连续。

1. $\mathrm{LCS}$ （最长公共子序列）

1.1 转移方程

给定两个序列 $A$ 、 $B$ ，设 $C[i, j]$ 为 $\mathrm{LCS}(A_i, B_j)$ 的长度，其中 $A_i$ 、 $B_j$ 分别表示 $A$ 从首元素到第 $i$ 个元素的一段、 $B$ 从首元素到第 $j$ 个元素的一段, $a_i$ 、 $b_i$ 分别表示 $A$ 中第 $i$ 个元素、 $B$ 中第 $j$ 个元素，序列 $A$ 和 $B$ 的长度分别为 $n$ 和 $m$ 。则 $\mathrm{LCS}$ 的状态转移方程为：

$C[i, j] = 0 \quad (i = 0 \vee j = 0 )$
$C[i, j] = C[i-1, j-1] + 1 \quad (i,j > 0 \wedge a_i = b_j)$
$C[i, j] = \mathrm{max}(C[i-1, j], C[i, j-1]) \quad (i,j > 0 \wedge a_i \neq b_j)$

若还要求 $\mathrm{LCS}$ 的个数，则可以设 $D[i, j]$ 为 $\mathrm{LCS}(A_i, B_j)$ 的个数，在上述转移方程求完 $C[i, j]$ 后，进一步求出 $D[i, j]$ ：

初始化： $D[i, j] = 1 \quad (i = 0 \vee j = 0)$
根据可转移到 $D[i, j]$ 的三个方向依次累加个数：

\begin{array}{l} D[i, j] = 0 \\ D[i, j] = D[i, j] + D[i-1, j-1] \quad (a_i = b_j) \\ D[i, j] = D[i, j] + D[i-1, j] \quad (C[i, j] = C[i-1, j]) \\ D[i, j] = D[i, j] + D[i, j-1] \quad (C[i, j] = C[i, j-1]) \\ D[i, j] = D[i, j] - D[i-1, j-1] \quad (C[i, j] = C[i-1, j-1]) \end{array}

若还要求出 $\mathrm{LCS}$ ，则可以根据 $C[i, j]$ 与 $C[i-1, j-1]$ 、 $C[i-1, j]$ 和 $C[i, j-1]$ 的大小关系来进行回溯，或者直接用数组记录各个长度的相等点（相等点指 $(i,j)$ ，其满足 $A_i = B_j$ ）。

1.2 分析

关于第一个转移方程：此转移方程比较好理解，最终结果为 $C[n, m]$ ，该算法时间和空间复杂度为 $O(nm)$ 。
关于第二个转移方程：我们发现求 $C[i, j]$ 时，其结果仅依赖三个方向的值，即 $C[i-1, j-1], C[i-1, j], C[i, j-1]$ 。也就是说， $LCS(A_i, B_j)$ 的结果来源于这三个方向，求 $C[i, j]$ 的过程只选取了最大长度，而没有考虑方案数。因此，我们可以用数组 $D[i, j]$ 来保存 $LCS(A_i, B_j)$ 的方案数。

当 $a_i = b_j$ 时，说明 $LCS(A_i, B_j)$ 可以来自于 $LCS(A_{i-1}, B_{j-1})$ ，因此 $D[i, j] = D[i, j] + D[i-1, j-1]$ 。

当 $C[i, j] = C[i-1, j]$ 时，说明 $LCS(A_i, B_j)$ 还可以来自于 $LCS(A_{i-1}, B_j)$ ，因此 $D[i, j] = D[i, j] + D[i-1, j]$ 。

当 $C[i, j] = C[i, j-1]$ 时，说明 $LCS(A_i, B_j)$ 还可以来自于 $LCS(A_i, B_{j-1})$ ，因此 $D[i, j] = D[i, j] + D[i, j-1]$ 。

但是我们会有一个疑问，即这三个方向是否存在重复方案数呢，即某个方向是来自于另一个方向的。此即当 $C[i, j] = C[i-1, j-1]$ 时，说明 $a_i \neq b_j$ ，此时 $D[i-1, j]$ 和 $D[i, j-1]$ 都重复统计了 $D[i-1, j-1]$ ，根据容斥原理，需要减去一个，即 $D[i, j] = D[i, j] - D[i-1, j-1]$ 。

对于上述还需要说明的是：

当 $a_i = b_j$ 时，易知 $C[i-1, j], C[i, j-1] \leq C[i-1, j-1] + 1$ 。且当 $C[i-1, j] = C[i-1, j-1] + 1$ 时，根据上述的法则可知，其方案数 $D[i-1, j]$ 必定不来自于 $D[i-1, j-1]$ ； $C[i, j-1]$ 同理，因此此时可以累加三者。

当 $a_i \neq b_j$ 时，由 $C[i,j]$ 的计算可知，此时 $D[i, j]$ 只来源于 $D[i-1, j]$ 和 $D[i, j-1]$ 。且当 $C[i-1, j-1] \lt C[i, j]$ 时， $D[i-1, j-1]$ 不对 $D[i, j]$ 造成贡献，此时 $D[i-1, j]$ 和 $D[i, j-1]$ 没有交叉，可直接累加；而当 $C[i-1, j-1] = C[i, j]$ 时，根据上述法则， $D[i, j]$ 会同时贡献 $D[i-1, j]$ 和 $D[i, j-1]$ ，因此 $D[i-1, j]$ 和 $D[i, j-1]$ 交叉了 $D[i-1, j-1]$ ，需要去除一份 $D[i-1, j-1]$ 。

最终结果即为 $D[n, m]$ ，综合的时间和空间复杂度仍为 $O(nm)$ 。

【注】此类二维动态规划的空间复杂度可以用滚动数组降为 $O(\max(n, m))$ 。

1.3 扩展

相较于用动态规划思想求 $\mathrm{LCS}$ 长度的复杂度为 $O(nm)$ ，求 $\mathrm{LIS}$ 长度的最优复杂度可以达到 $O(n \log{n})$ （见下文）。幸运的是部分 $\mathrm{LCS}$ 问题可以用 $\mathrm{LIS}$ 来解。

在 $\mathrm{LCS}$ 中，两个序列中的元素仅表示一种符号，用来判定是否相等的符号，对于符号背后具体的数值对 $\mathrm{LCS}$ 的结果并没有影响。
在 $\mathrm{LIS}$ 中，是需要考虑序列元素的数值大小关系的。

若 $\mathrm{LCS}$ 的两个序列中的其中一个满足元素互异条件，则可以用 $\mathrm{LIS}$ 来解。

在此类 $\mathrm{LCS}$ 中，不防假设序列 $A$ 中元素是互异的，设序列 $A$ 的长度为 $n$ ，则我们可以考虑将 $A$ 的元素按照出现顺序依次映射到 $1 \ldots n$ 上，从而得到 $A$ 中元素与数值的一一对应关系。然后根据 $A$ 元素的映射表，来计算序列 $B$ 元素对应的映射值；对于在 $B$ 中存在而不在 $A$ 中存在的元素，直接舍弃即可，因为它们必然不会出现在 $\mathrm{LCS}$ 中。
如此，映射完 $B$ 得到的数值序列设为 $C$ ，其长度为 $m$ 。则此时只需要计算序列 $C$ 的 $\mathrm{LIS}$ 即可。这是因为序列 $A$ 映射后的序列是一个递增的数值序列，因此 $A$ 和 $C$ 的公共子序列也是递增子序列。由于 $C$ 中所有数值都在 $A$ 的映射表中，故 $C$ 的最长递增子序列也是二者的最长公共子序列，因此只需要求序列 $C$ 的最长递增子序列即可。

1.4 代码

仅求 $\mathrm{LCS}$ 长度，时间复杂度为 $O(nm)$ ，空间复杂度为 $O(\max(n, m))$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCS_
#define _LCS_
#define ll int
#define ele char
#define MAXN 100005

// 最长公共子序列
struct LCS {
    // 输入参数
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    LCS(): n(0), m(0) {}
    // 动态规划求 LCS 长度
    // 复杂度 O(nm)
    ll length() {
        // 降维操作：n*m 维降为 2*m 维
        // 以下两个数组对应 lcs 长度的二维数组中相邻上下两行 
        ll uplen[MAXN] = {0}, downlen[MAXN] = {0};
        ll *puplen = uplen, *pdownlen = downlen;
        for(ll i = 1; i <= n; ++i) {
            for(ll j = 1; j <= m; ++j) {
                if(A[i-1] == B[j-1]) {
                    pdownlen[j] = puplen[j-1] + 1;
                } else {
                    pdownlen[j] = max(puplen[j], pdownlen[j-1]);
                }
            }
            swap(puplen, pdownlen);
        }
        return puplen[m];
    }
};
#endif

若 $\mathrm{LCS}$ 两个序列中至少一个（假设为 $A$ ）满足元素互异条件，则求此类 $\mathrm{LCS}$ 长度的时间复杂度为 $O(n + m \log{m})$ ，空间复杂度为 $O(\max(n, m))$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCS_
#define _LCS_
#define ll int
#define ele char
#define MAXN 100005

// 最长公共子序列
struct LCS{
    
    // 输入参数
    ll n, m;
    ele A[MAXN], B[MAXN];       // 序列 A 满足元素互异条件
    LCS(): n(0) {}
    // 离散化+二分+栈
    // 复杂度 O(n + mlogm)
    ll length() {
        unordered_map <ele,ll> mp;
        // 离散化序列 A
        for(ll i = 0; i < n; ++i) {
            mp[A[i]] = i;
        }
        // 离散化序列 B
        ll cnt = 0;
        ll len[m];
        for(ll i = 0; i < m; ++i) {
            if(mp.count(B[i]) > 0) {
                len[cnt++] = mp[B[i]];
            }
        }
        // 二分+栈求 LIS 长度
        vector <ll> lis;
        lis.push_back(len[0]);
        for(ll i = 1; i < cnt; ++i) {
            if(len[i] > lis.back()) {
                lis.push_back(len[i]);
            } else {
                ll pos = lower_bound(lis.begin(), lis.end(), len[i]) - lis.begin();
                lis[pos] = min(lis[pos], len[i]);
            }
        }
        return lis.size();
    }
};
#endif

既求 $\mathrm{LCS}$ 长度，又求 $\mathrm{LCS}$ 的个数，时间复杂度为 $O(nm)$ ，空间复杂度为 $O(\max(n, m))$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCS_
#define _LCS_
#define ll int
#define ele char
#define MAXN 10005

// 最长公共子序列
struct LCS {
    // 输入参数
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    // 中间 & 输出参数
    ll mxlen, mxcnt;            // 保存最长子序列长度和个数
    LCS(): n(0), m(0), mxlen(0), mxcnt(0) {}
    // 动态规划求 LCS 长度和个数
    // 复杂度 O(nm)
    void dp() {
        // 滚动数组
        // 以下两个数组对应 lcs 长度的二维数组中相邻上下两行 
        ll uplen[MAXN] = {0}, downlen[MAXN] = {0};
        ll *puplen = uplen, *pdownlen = downlen;
        // 以下两个数组对应 lcs 个数的二维数组中相邻上下两行
        ll upcnt[MAXN] = {0}, downcnt[MAXN] = {0};
        ll *pupcnt = upcnt, *pdowncnt = downcnt;
        for(ll i = 0; i <= m; ++i) {
            pupcnt[i] = 1;
        }
        pdowncnt[0] = 1;
        // 动态规划求 LCS 长度和个数
        for(ll i = 1; i <= n; ++i) {
            for(ll j = 1; j <= m; ++j) {
                pdowncnt[j] = 0;    // 初始化
                pdownlen[j] = max(puplen[j], pdownlen[j-1]);
                if(A[i-1] == B[j-1]) {
                    pdownlen[j] = puplen[j-1] + 1;
                    pdowncnt[j] = pupcnt[j-1];
                }
                if(pdownlen[j] == puplen[j]) {
                    pdowncnt[j] = pdowncnt[j] + pupcnt[j];
                }
                if(pdownlen[j] == pdownlen[j-1]) {
                    pdowncnt[j] = pdowncnt[j] + pdowncnt[j-1];
                }
                if(pdownlen[j] == puplen[j-1]) {
                    pdowncnt[j] = pdowncnt[j] - pupcnt[j-1];
                }
            }
            swap(puplen, pdownlen);
            swap(pupcnt, pdowncnt);
        }
        mxlen = puplen[m];
        mxcnt = pupcnt[m];
    }
};
#endif

既求 $\mathrm{LCS}$ 长度，又求一个 $\mathrm{LCS}$ ，时/空间复杂度为 $O(nm)$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCS_
#define _LCS_
#define ll int
#define ele char
#define MAXN 1005

// 最长公共子序列
struct LCS {
    // 输入参数
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    // 中间 & 输出参数
    ll mxlen;                   // 记录 LCS 的长度
    ll len[MAXN][MAXN];         // 记录 DP 过程 A0..i 和 B0..j 的 LCS 长度
    stack <ele> path;            // 记录一个 LCS
    LCS(): n(0), m(0), mxlen(0) {
        memset(len, 0, sizeof(len));
    }
    // 动态规划求 LCS 长度
    // 复杂度 O(nm)
    void dp() {
        for(ll i = 1; i <= n; ++i) {
            for(ll j = 1; j <= m; ++j) {
                if(A[i-1] == B[j-1]) {
                    len[i][j] = len[i-1][j-1] + 1;
                } else {
                    len[i][j] = max(len[i-1][j], len[i][j-1]);
                }
            }
        }
        mxlen = len[n][m];
    }
    // 回溯记录一个 LCS 
    void getlcs() {
        if(mxlen == 0) {
            dp();
        }
        ll lcslen = mxlen;
        ll i = n-1, j = m-1;
        while(lcslen > 0) {
            if(A[i] == B[j]) {
                path.push(A[i]);
                --i, --j;
                --lcslen;
            } else if(len[i+1][j+1] == len[i][j+1]) {
                --i;
            } else {
                --j;
            }
        }
    }
};
#endif

既求 $\mathrm{LCS}$ 长度和个数，又求所有的 $\mathrm{LCS}$ （包括相同的），时/空间复杂度都是指数的。

【注】若要求所有不同的 $\mathrm{LCS}$ ，只需用 unordered_map 来记录 $\mathrm{LCS}$ 是否已经打印过，打印时判定哈希值是否存在即可。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCS_
#define _LCS_
#define ll int
#define ele char
#define MAXN 1005
#define MAXM 10005

// 最长公共子序列
struct LCS {
    // 边（前向星）
    struct Edge{
        ll len;                 // 从起点到当前边的路径长度
        ll next, to;    
        ele element;            // to 端点对应的序列 element
    };
    // 记录 A 序列和 B 序列相等点
    struct MAPPING{
        ll apos, bpos;          // 对应 A、B 序列的下标
        ll count;               // 记录从该相等点往后可以匹配出多少个 LCS
        MAPPING(ll _apos, ll _bpos, ll _count): apos(_apos), bpos(_bpos), count(_count) {}
        // 重载相等点 < 操作符
        // 用来判定两个相等点是否存在前后依赖关系
        bool operator < (const MAPPING mp) const {
            return apos < mp.apos && bpos < mp.bpos;
        }
    };
    // 输入参数
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    // 中间 & 输出参数
    ll mxlen, mxcnt;            // 记录 LCS 的长度和个数
    ll len[MAXN][MAXN];         // 记录 DP 过程 A0..i 和 B0..j 的 LCS 长度
    vector <MAPPING> lcs[MAXN];
    // 有向图存储所有 LCS
    ll vcnt, ecnt;              // 动态开点、开边
    ll head[MAXM];   
    ll vertex[MAXN][MAXN];      // 记录每个点对应的图中的顶点           
    Edge graph[MAXM];
    // 添加有向边
    void addedge(ll u, ll v, ll len, ele e) {
        graph[ecnt].element = e;
        graph[ecnt].len = len;
        graph[ecnt].to = v;
        graph[ecnt].next = head[u];
        head[u] = ecnt++;
    }
    LCS(): n(0), m(0), mxlen(0), mxcnt(0) {
        vcnt = 1, ecnt = 0;
        memset(len, 0, sizeof(len));
        memset(head, -1, sizeof(head));
        memset(vertex, 0, sizeof(vertex));
    }
    // 动态规划求 LCS 长度
    // 复杂度 O(nm)
    void dp() {
        for(ll i = 1; i <= n; ++i) {
            for(ll j = 1; j <= m; ++j) {
                if(A[i-1] == B[j-1]) {
                    len[i][j] = len[i-1][j-1] + 1;
                    lcs[len[i][j]].push_back(MAPPING(i-1, j-1, 0));
                } else {
                    len[i][j] = max(len[i-1][j], len[i][j-1]);
                }
            }
        }
        mxlen = len[n][m];
    }
    // 回溯记录所有 LCS 
    void getlcss() {
        if(mxlen == 0) {
            dp();
        }
        // 用 vector 记录各个长度的相等点
        // 求以序列 B 各个元素开头的 LCS 个数
        // 同时用有向图结构存储所有 LCS 的连接关系
        for(ll i = 0; i < lcs[mxlen].size(); ++i) {
            // 从后往前统计 LCS 个数
            lcs[mxlen][i].count = 1;
            // 动态开点
            vertex[lcs[mxlen][i].apos][lcs[mxlen][i].bpos] = vcnt++;
        }
        for(ll i = mxlen - 1; i > 0; --i) {
            // 计算相邻长度的相等点对应的 LCS 个数
            for(ll j = 0; j < lcs[i+1].size(); ++j) {
                // 只统计能够形成 LCS 的相等点
                if(lcs[i+1][j].count > 0) {
                    ll napos = lcs[i+1][j].apos, nbpos = lcs[i+1][j].bpos;
                    for(ll k = 0; k < lcs[i].size(); ++k) {
                        if(lcs[i][k] < lcs[i+1][j]) {
                            lcs[i][k].count = lcs[i][k].count + lcs[i+1][j].count;
                            // 存储有向边
                            ll apos = lcs[i][k].apos, bpos = lcs[i][k].bpos;
                            if(!vertex[apos][bpos]) {
                                // 动态开点
                                vertex[apos][bpos] = vcnt++;
                            }
                            addedge(vertex[apos][bpos], vertex[napos][nbpos], i+1, A[napos]);
                        }
                    }
                }
            }
        }
        mxcnt = 0;
        for(ll j = 0; j < lcs[1].size(); ++j) {
            if(lcs[1][j].count > 0) {
                mxcnt += lcs[1][j].count;
                // 存储有向边
                ll apos = lcs[1][j].apos, bpos = lcs[1][j].bpos;
                addedge(0, vertex[apos][bpos], 1, A[apos]);
            }
        }
    }
    // 打印所有 LCS
    void printlcss() {
        if(mxcnt == 0) {
            getlcss();
        }
        // 用栈遍历整个 LCS 有向图的边
        stack <ll> clss;
        for(ll e = head[0]; e != -1; e = graph[e].next) {
            clss.push(e);
        }
        // 用向量记录每一个 LCS
        vector <ele> print;
        while(!clss.empty()) {
            ll e = clss.top(); clss.pop();
            ll u = graph[e].to;
            print.resize(graph[e].len - 1);
            print.push_back(graph[e].element);
            // 判断是否已经形成一个 LCS
            if(head[u] == -1) {
                for(ll i = 0; i < print.size(); ++i) {
                    printf("%c", print[i]);
                }
                printf("\n");
            } else {
                for(ll e = head[u]; e != -1; e = graph[e].next) {
                    clss.push(e);
                }
            }
        }
    }
};
#endif

2. $\mathrm{LIS}$ （最长递增子序列）

2.1 状态转移方程

这里考虑严格递增（不严格递增类似）。给定一个序列 $A$ ，设 $a_i$ 表示 $A$ 中的第 $i$ 个元素， $I[i]$ 为以 $a_i$ 结尾最长递增子序列的长度，假定 $a_0 \lt a_i, \forall i \gt 0$ ，则其状态转移方程为：

$I[i] = 0 \quad (i = 0)$
$I[i] = \mathrm{max}(I[j] + 1) \quad (0 \leq j \lt i \wedge a_i \gt a_j)$

2.2 分析

若只是要求求出 $\mathrm{LIS}$ 的长度，则可用一个栈来储存 $\mathrm{LIS}$ ，并结合二分来维护 $\mathrm{LIS}$ ，该栈的最后一个元素为最长 $\mathrm{LIS}$ 的尾元素，栈长即为 $\mathrm{LIS}$ ，算法复杂度为 $O(n \log{n})$ 。
若要求输出 $\mathrm{LIS}$ ，则可以考虑求 $A$ 和 $\mathrm{sort}(A)$ 的 $\mathrm{LCS}$ ，此 $\mathrm{LCS}$ 即为 $A$ 的最长不减子序列，进一步得到 $\mathrm{LIS}$ 只需剔除那些多余相等的元素，算法复杂度为 $O(n^2)$ 。

2.3 代码

仅求 $\mathrm{LIS}$ 的长度，时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LIS_
#define _LIS_
#define ll int
#define ele char
#define MAXN 100005

// 最长递增子序列
struct LIS{
    ll n;
    ele A[MAXN];
    LIS(): n(0) {}
    // 动态规划求 LIS 长度
    // 复杂度 O(n^2)
    ll length() {
        ll rst = 0;
        ll lislen[n] = {0};
        for(ll i = 1; i <= n; ++i) {
            lislen[i] = 1;
            for(ll j = 1; j <= i; ++j) {
                if(A[j-1] < A[i-1]) {
                    lislen[i] = max(lislen[i], lislen[j]+1);
                }
            }
            rst = max(rst, lislen[i]);
        }
        return rst;
    }
};
#endif

仅求 $\mathrm{LIS}$ 的长度，时间复杂度为 $O(n \log{n})$ ，空间复杂度为 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LIS_
#define _LIS_
#define ll int
#define ele char
#define MAXN 100005

// 最长递增子序列
struct LIS{
    ll n;
    ele A[MAXN];
    LIS(): n(0) {}
    // 二分+栈求 LIS 长度
    // 复杂度 O(nlogn)
    ll length() {
        vector <ll> lis;
        lis.push_back(A[0]);
        for(ll i = 1; i < n; ++i) {
            if(A[i] > lis.back()) {
                lis.push_back(A[i]);
            } else {
                vector <ll>::iterator it = lower_bound(lis.begin(), lis.end(), A[i]);
                *it = A[i];
            }
        }
        return lis.size();
    }
};
#endif

若要求输出 $\mathrm{LIS}$ ，则参考求 $\mathrm{LCS}(A, \mathrm{sort}(A))$ ，代码参考 $\mathrm{LCS}$ 部分。

3. $\mathrm{LCIS}$ （最长递增公共子序列）

3.1 状态转移方程

此问题可以看成是 $\mathrm{LIS}$ 问题和 $\mathrm{LCS}$ 问题的重叠。给定两个序列 $A$ 、 $B$ ，设序列 $A$ 和 $B$ 的长度分别为 $n$ 和 $m$ ， $CI[i][j]$ 为 $A$ 中前 $i$ 个元素， $B$ 中前 $j$ 个元素且以 $B[j]$ 结尾的 $\mathrm{LCIS}$ ，则其状态转移方程为：

$CI[i][j] = 0 \quad (i = 0 \vee j = 0)$
$CI[i][j] = CI[i-1][j] \quad (A[i] \neq B[j])$
$CI[i][j] = \mathrm{max}_{1 \leq k \leq j - 1 \wedge B[k] \lt A[i]}(CI[i-1][k]) + 1 \quad (A[i] = B[j])$

由此状态转移方程，可以写出最小时间复杂度为 $O(nm)$ 的算法。同样用二维数组（或一维滚动数组，参考附录中「有关空间复杂度的降低」）。

3.2 分析

如何理解上述状态转移方程：

对于第一个等式，如果 $A[i] \neq B[j]$ ，而 $CI[i][j]$ 是以 $B[j]$ 为结尾的 $\mathrm{LCIS}$ 长度，则必有 $CI[i][j] = CI[i-1][j]$ 。
对于第二个等式，如果 $A[i] = B[j]$ ，则 $CI[i][j]$ 应该为 $CI[i-1][1] \sim CI[i-1][j-1]$ 中满足 $B[k] \lt A[i]$ （满足递增条件）的最大值 $+1$ 。在寻找 $\mathrm{max}(CI[i-1][k])$ 的时候，其实可以在求 $CI[i-1][j-1]$ 时求出，即每次计算 $CI[i][j]$ 的时候，同时计算出 $\mathrm{max}(CI[i][k])$ 。这样可以将时间复杂度降为 $O(nm)$ 。具体实现步骤如下：

初始化 $\mathrm{max} = 0$ ，内层循环 $j = 1 : m$ 。

如果 $A[i] \gt B[j] \wedge \mathrm{max} \lt CI[i-1][j]$ ，则 $\mathrm{max} = CI[i-1][j]$ 。

这样，当循环到 $A[i] = B[j]$ 时， $\mathrm{max}$ 即为 $\mathrm{max}(CI[i-1][k])$ 。为什么是 $A[i] > B[j]$ 呢，因为这个时候 $A[i]$ 为考虑中的公共元素，当它大于 $B[j]$ 时，说明 $B[j]$ 后面可能有和它相等的元素，故 $A[i]$ 可能接到 $B[j]$ 的后面。若是 $A[i] \lt B[j]$ ，则 $A[i]$ 不可能接到 $B[j]$ 的后面（因为递增子序列）。

这个问题如果允许复杂度再大一点话，其实是可以转化为三个序列求 $\mathrm{LCS}$ 的问题，这三个序列分别是 $A$ ， $B$ ， $\mathrm{sort}(A)$ （或 $\mathrm{sort}(B)$ ）。若 $A$ 中有重复元素，则需剔除 $\mathrm{sort(A)}$ 中的重复元素（不防记为 $C$ ），再求三者的 $\mathrm{LCS}(A,B,C)$ （利用三维数组实现，若用滚动数组实现则可以降为二维，参考附录中「有关空间复杂度的降低」）。可以利用反证法给出具体证明：

显然是 $A,B$ 的递增公共子序列，倘若其不是 $\mathrm{LCIS}(A,B)$ ：

要么是 $|\mathrm{LCIS}(A,B)| \gt |\mathrm{LCS}(A,B,C)|$ ，这显然不可能，因为 $\mathrm{LCIS}(A,B)$ 是 $A,B$ 的递增子序列，所以也是 $C$ 的子序列，因此 $\mathrm{LCIS}(A,B)$ 是 $A,B,C$ 的公共子序列，因此 $|\mathrm{LCIS}(A,B)| \leq |\mathrm{LCS}(A,B,C)|$ ，即命题矛盾。

要么是 $|\mathrm{LCIS}(A,B)| \lt |\mathrm{LCS}(A,B,C)|$ ，由于 $\mathrm{LCS}(A,B,C)$ 是 $A,B$ 的递增子序列，因此 $|\mathrm{LCIS}(A,B)| \geq |\mathrm{LCS}(A,B,C)|$ ，即命题矛盾。

综上， $\mathrm{LCIS}(A,B) = \mathrm{LCS}(A,B,C)$ 。

3.3 代码

既求 $\mathrm{LCIS}$ 长度，又求 $\mathrm{LCIS}$ 个数，时间复杂度 $O(nm)$ ，空间复杂度 $O(\mathrm{max}(n, m))$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCIS_
#define _LCIS_
#define ll int
#define ele int
#define MAXN 10005

// 最长公共子序列
struct LCIS {
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    ll mxlen, mxcnt;            // 保存最长公共递增子序列长度和个数
    LCIS(): n(0), m(0), mxlen(0), mxcnt(0) {}
    // 动态规划求 LCS 长度和个数
    // 复杂度 O(nm)
    void dp() {
        // 滚动数组
        // 以下两个数组对应 lcis 长度的二维数组中相邻上下两行 
        ll uplen[MAXN] = {0}, downlen[MAXN] = {0};
        ll *puplen = uplen, *pdownlen = downlen;
        // 以下两个数组对应 lcis 个数的二维数组中相邻上下两行
        ll upcnt[MAXN] = {0}, downcnt[MAXN] = {0};
        ll *pupcnt = upcnt, *pdowncnt = downcnt;
        for(ll i = 1; i <= n; ++i) {
            ll k = 0;
            ll lencnt[MAXN] = {0};
            lencnt[0] = 1;
            for(ll j = 1; j <= m; ++j) {
                if(A[i-1] == B[j-1]) {
                    pdownlen[j] = puplen[k] + 1;
                    pdowncnt[j] = lencnt[puplen[k]];
                } else {
                    pdownlen[j] = puplen[j];
                    pdowncnt[j] = pupcnt[j];
                    if(A[i-1] > B[j-1]) {
                        if(puplen[j] >= puplen[k]) {
                            k = j;
                            lencnt[puplen[j]] += pupcnt[j];
                        }
                    }
                }
            }
            swap(pdownlen, puplen);
            swap(pdowncnt, pupcnt);
        }
        // 求 LCIS 长度
        mxlen = 0;
        for(ll j = 1; j <= m; ++j) {
            mxlen = max(mxlen, puplen[j]);
        }
        // 求 LCIS 个数
        mxcnt = 0;
        for(ll j = 1; j <= m; ++j) {
            if(puplen[j] == mxlen) {
                mxcnt += pupcnt[j];
            }
        }
    }
};
#endif

既求 $\mathrm{LCIS}$ 长度，又要求输出一个 $\mathrm{LCIS}$ ，时空间复杂度为 $O(nm)$ 。

#include <bits/stdc++.h>
using namespace std;

#ifndef _LCIS_
#define _LCIS_
#define ll int
#define ele int
#define MAXN 555
#define MAXELE 0x7fffffff   // 序列元素的最大值

// 最长公共子序列
struct LCIS {
    ll n, m;                    // 对应 A、B 两序列长度
    ele A[MAXN], B[MAXN];       // A、B 两序列
    ll len[MAXN][MAXN];         // LCIS 二维长度数组
    ll mxlen;                   // 保存最长公共递增子序列长度
    stack <ele> path;           // 一个 LCIS
    LCIS(): n(0), m(0), mxlen(0) {
        memset(len, 0, sizeof(len));
    }
    // 动态规划求 LCS 长度
    // 复杂度 O(nm)
    void dp() {
        for(ll i = 1; i <= n; ++i) {
            ll k = 0;
            for(ll j = 1; j <= m; ++j) {
                if(A[i-1] == B[j-1]) {
                    len[i][j] = len[i-1][k] + 1;
                } else {
                    len[i][j] = len[i-1][j];
                    if(A[i-1] > B[j-1]) {
                        if(len[i-1][j] > len[i-1][k]) {
                            k = j;
                        }
                    }
                }
            }
        }
        mxlen = 0;
        for(ll j = 1; j <= m; ++j) {
            mxlen = max(mxlen, len[n][j]);
        }
    }
    // 回溯求一个 LCIS
    void getlcis() {
        if(mxlen == 0) {
            dp();
        }
        ll i = n, j = m;
        ll curlen = mxlen;
        ele mxele = MAXELE;
        while(curlen > 0) {
            if(len[i][j] != curlen || B[j-1] >= mxele) {
                --j;
            } else {
                if(A[i-1] != B[j-1]) {
                    --i;
                } else {
                    path.push(B[j-1]);
                    mxele = B[j-1];
                    --curlen;
                    --i, --j;
                }
            }
        }
    }
};
#endif

附录

有关空间复杂度的降低

对于上面三种问题，若采用了数组来实现状态转移，且是逐行（或逐列）扫描，则可降低一维，因为上面三种问题的状态转移数组的每一位的求解时均只是利用到该位的左上及其正上和正左的元素，而且最终的答案在最后的那一行（或列）中，故可以减去一维，实现逐行（或逐列）重复扫描，从而降低了空间复杂度，这种降维方法也称为滚动数组。

Technique ACM 算法动态规划

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

凸包算法上一篇

BSGS算法下一篇

概念

1. LCS\mathrm{LCS}LCS（最长公共子序列）