1. 问题定义与模型定位两个经典模型的交叉路口最长公共上升子序列LCISLongest Common Increasing Subsequence是动态规划题目里一个非常经典的综合题型。它把两个看似独立的问题——最长上升子序列LIS和最长公共子序列LCS——强行揉在了一起给定两个序列 A 和 B要求找出一个最长的子序列它既是 A 和 B 的公共子序列又满足严格单调递增。我第一次见到这个题是在刷题群里群友发了一道“求两个数组的最长公共上升子序列长度”的题。当时第一反应是“这不就是先求 LCS 再对结果求 LIS 吗”——这个思路看起来顺理成章但实际上是个陷阱。因为 LCS 的结果是一个集合你没法保证从这个集合里选出的子序列在原序列中的相对位置还能满足另一个序列的顺序约束。先明确问题本身的输入输出输入两个序列 A[1..n] 和 B[1..m]长度通常到 1e3 甚至 1e4 级别。输出一个整数表示最长的公共上升子序列的长度。这里要特别注意“上升”的定义严格递增即子序列中任意相邻两个位置满足 a[i] a[j]i j相等的元素不能重复计入。从模型归属上看LCIS 属于“线性 DP 中的双序列模型”它在状态设计上借鉴了 LCS 的“二维前缀”思想又在转移逻辑上吸收了 LIS 的“以某个元素结尾”的经典套路。这也是为什么很多教材把它放在 LIS 和 LCS 之后作为进阶题——它要求你同时掌握两种模型的本质而不是机械地背诵转移方程。我见过不少初学者在学完 LIS 和 LCS 后觉得自己“会 DP 了”结果一遇到 LCIS 就卡住。根本原因在于LIS 的状态是“以元素结尾”LCS 的状态是“前缀匹配”这两个状态维度在 LCIS 中需要合并成一个新的状态表示而这个合并过程恰恰是这道题思维含量的核心。下一节我会详细拆解这个状态设计的过程以及中间有哪些容易踩的坑。2. 从 LIS 和 LCS 到 LCIS状态设计的演进逻辑2.1 为什么不能直接套用 LCS 的状态定义LCS 的标准做法是定义 dp[i][j] 表示“A 的前 i 个元素和 B 的前 j 个元素的 LCS 长度”转移时比较 A[i] 和 B[j] 是否相等不相等就取 max(dp[i-1][j], dp[i][j-1])。这个状态定义成熟、简单但它有一个前提假设我们只关心两个前缀的匹配结果不关心匹配出的子序列在末尾处的具体取值。而 LCIS 要求子序列递增这意味着我们必须知道当前已匹配子序列的最后一个元素是多少才能判断能否继续接上新的元素。举个例子A [2, 3, 4]B [2, 4, 3]。如果只看 LCS 长度答案是 2可以取 [2, 4] 或 [2, 3]。但要算 LCIS[2, 4] 是合法的递增序列[2, 3] 虽然也是递增但它在 B 中的顺序是 2 → 3B[1] 到 B[3]合法不过 [4, 3] 这种就不行因为不是递增。这个例子说明仅仅知道“长度”还不够必须知道末尾元素的具体值。2.2 引入“以 B[j] 结尾”的状态维度既然需要知道末尾元素一种很自然的想法是模仿 LIS 的经典状态定义 f[i][j] 表示“A 的前 i 个元素B 的前 j 个元素且以 B[j] 结尾的 LCIS 长度”。为什么是“以 B[j] 结尾”而不是“以 A[i] 结尾”因为公共子序列中的最后一个元素它同时在 A 和 B 中都有位置。如果我们只记录“以 A[i] 结尾”那么在转移时需要同时知道 B 中的位置信息两个结尾位置都需要维护状态维度会膨胀到三维甚至四维。而统一用“以 B[j] 结尾”来收束就可以把 B 的位置信息融入状态本身转移时只需要枚举 A 那边的匹配位置即可。这里有个关键点f[i][j] 中的“以 B[j] 结尾”意味着当前找到的 LCIS 必须包含 B[j] 这个元素并且 B[j] 正好是它最后一个元素。如果 A[i] ! B[j]那以 B[j] 结尾的 LCIS 在枚举到 A[i] 时A[i] 无法作为新的末尾元素加入所以 f[i][j] 只能继承 f[i-1][j]也就是不选 A[i] 时的最优值。可能有人会问为什么不定义成“以 A[i] 结尾”呢我也试过这个对称版本定义 g[i][j] 表示“A 的前 i 个元素中、以 A[i] 结尾且与 B 的前 j 个元素构成的 LCIS 长度”。这样定义在转移时会遇到一个麻烦当 A[i] B[j] 时我们需要在 B 的前 j-1 个元素中找一个 b[k] A[i] 且能与 A 的前 i-1 个元素构成最长上升子序列的位置这个“在 B 中找小于当前值的位置”需要额外扫描代码写起来绕而且不容易扩展到输出方案的场景。相比之下以 B[j] 结尾更自然——枚举 A 的过程中天然维护了“A 中末尾值”的信息。2.3 状态转移方程的完整推导沿用上面的定义f[i][j] 有两大类情况情况一A[i] ! B[j]此时 B[j] 不可能作为合并后的结尾元素因为 A 中当前位置不是这个值公共子序列需要两个序列中都有这个元素。所以 f[i][j] f[i-1][j]这个转移的含义是既然 A[i] 帮不上忙那就看 A 的前 i-1 个元素能凑出多长的以 B[j] 结尾的公共上升子序列。情况二A[i] B[j]此时可以将 B[j] 作为当前 LCIS 的最后一个元素。那么需要在 A 的前 i-1 个元素中找到一个可以接在 B[j] 前面的元素——也就是某个 B[k]k j满足 B[k] B[j]并且以该 B[k] 结尾的 LCIS 长度最大。于是 f[i][j] max(1, max_{k j 且 B[k] A[i]} (f[i-1][k] 1))注意这里用 A[i] 而不是 B[j] 做比较基准因为 A[i] B[j]二者等价。但写成 A[i] 更直观地体现了“新元素要大于前一个末尾元素”的单调性要求。理论上讲这个转移的时间复杂度是 O(n * m^2)i 从 1 到 nj 从 1 到 m内层还要枚举 k 从 1 到 j-1。当 n 和 m 都在 1000 以上时1e9 级别的运算量在大多数在线评测系统上会超时。这也是为什么很多博客直接给出 O(n * m) 的优化版本后面的章节我会重点讲这个优化技巧。3. 核心细节解析与 O(n*m) 优化3.1 朴素版本的瓶颈在哪里先写一个朴素版本的伪代码方便对照理解for i 1 to n: for j 1 to m: if A[i] ! B[j]: f[i][j] f[i-1][j] else: f[i][j] 1 for k 1 to j-1: if B[k] A[i]: f[i][j] max(f[i][j], f[i-1][k] 1)仔细看第三层循环它做的是“在 j 之前的所有 B[k] 中找满足 B[k] A[i] 的最大 f[i-1][k]”。注意这个最大值只和 i 以及 A[i] 有关和当前 j 的关系只有一个j 每次多一个候选位置 B[j]。当我们固定 i从 j 1 往 j m 扫的时候可以顺便维护一个变量 maxv它表示“当前已经扫过的 B[1..j-1] 中满足 B[k] A[i] 的 max f[i-1][k]”。这样在 A[i] B[j] 时直接查 maxv 就能得到 f[i][j] 的值不需要再扫一遍 k。3.2 用滚动变量维护前缀最优值具体做法如下for i 1 to n: maxv 0 // 表示 B[1..j-1] 中满足 B[k] A[i] 的最大 f[i-1][k] for j 1 to m: if B[j] A[i]: maxv max(maxv, f[i-1][j]) if A[i] B[j]: f[i][j] maxv 1 else: f[i][j] f[i-1][j]这里的关键在于第二个条件判断B[j] A[i]必须在判断相等之前更新 maxv——因为我们要找的是“严格小于 A[i]”的候选不能把等于 A[i] 的也算进去否则会出现非严格递增的错误结果。有人可能会问maxv 是每个 i 重新初始化为 0 的这个 0 有什么含义它代表“空子序列”的长度也就是当找不到任何 B[k] A[i] 时我们可以用 A[i] 单独作为一个长度为 1 的子序列的开头或唯一元素。这个设计对应了转移方程里的“max(1, ...)”部分。为了更直观地理解这个优化我画个时间线i 固定时j 从 1 扫到 mmaxv 不断累加信息每当发现 B[j] A[i]就把 f[i-1][j] 加入候选池。当遇到 A[i] B[j] 时前面已经积累的 maxv 就是最优前驱长度。这样就省掉了第三层循环总复杂度降为 O(n * m)。3.3 状态转移的两种写法对比与边界处理网上还有另一种写法先处理不相等的情况再处理相等的情况for i 1 to n: maxv 0 for j 1 to m: // 先更新 maxv if B[j] A[i]: maxv max(maxv, f[i-1][j]) // 再处理当前状态 f[i][j] f[i-1][j] if A[i] B[j]: f[i][j] max(f[i][j], maxv 1)这两种写法在结果上等价但第二种写法更“安全”——它保证了不管 A[i] 是否等于 B[j]f[i][j] 至少能继承 f[i-1][j]不会因为遗漏继承而导致状态丢失。边界情况处理上建议f[0][j] 和 f[i][0] 都初始化为 0因为空序列的长度是 0。如果题目允许非严格递增即允许 b[k] A[i]把第一个条件改成 B[j] A[i] 即可。但大多数经典 LCIS 题目要求严格递增务必看清题意。我在实际做题时遇到过几次边界翻车一次是把第二个判断写成了 if (B[j] A[i]) maxv max(maxv, f[i-1][j]); if (B[j] A[i]) f[i][j] maxv 1; 看着没问题但当 maxv 还是 0 时f[i][j] 会被赋成 1这本身是对的可是如果 A[i] B[j] 且前面已经有更长的子序列呢由于 maxv 是在 j 循环中逐步更新的只要更新顺序对先更新 maxv 再计算当前 j就没问题。但若把这两行写反了就会漏掉 B[j] 自身这个候选导致答案偏小。这个细节非常隐蔽建议大家在本地多跑几个用例验证。4. 手把手推导一个完整用例的模拟过程4.1 数据准备用课程里常说的小例子A [2, 3, 1, 4, 2, 5]B [1, 2, 3, 2, 4, 5]长度均为 6。肉眼扫一遍能发现的最长公共上升子序列应该是 [2, 3, 4, 5]长度 4。注意[2, 3, 4, 5] 在 A 中的位置是 A[1], A[2], A[4], A[6]在 B 中的位置是 B[2], B[3], B[5], B[6]都保持相对顺序且严格递增。下面我们用滚动变量法模拟一遍 DP 过程。下表中每一行代表一个 i即 A 的第 i 个元素处理完后的状态每一列代表 j即 B 的前 j 个元素。为了简洁我只列出关键几步的 f 值变化。4.2 逐行模拟的关键步骤初始化f[0][1..6] 全为 0。i 1A[1] 2。maxv 0。j 1B[1] 1 2所以 maxv max(0, f[0][1]) 0。B[1] ! A[1]所以 f[1][1] f[0][1] 0。j 2B[2] 2。首先 B[2] A[1]不成立2 2 为假maxv 保持 0。B[2] A[1] 成立所以 f[1][2] maxv 1 1。j 3B[3] 3不小于 2maxv 为 0不相等f[1][3] f[0][3] 0。j 4B[4] 2不小于 2不相等A[1] 2f[1][4] f[0][4] 0。j 5B[5] 4不小于 2f[1][5] 0。j 6B[6] 5不小于 2f[1][6] 0。这个 i 处理完f[1][2] 1 是唯一非零的含义是只考虑 A 的前 1 个元素 {2}和 B 的前 6 个元素能构成的以 B[2] 2 结尾的 LCIS 就是 [2]长度 1。i 2A[2] 3。j 1B[1] 1 3maxv max(0, f[1][1]) 0。不相等f[2][1] f[1][1] 0。j 2B[2] 2 3maxv max(0, f[1][2]) 1。不相等2 ! 3f[2][2] f[1][2] 1。j 3B[3] 3不大于 3maxv 保持 1。B[3] A[2] 成立f[2][3] maxv 1 2。这意味着以 B[3]3 结尾的 LCIS 可以是 [2, 3]长度为 2。j 4B[4] 2 3maxv max(1, f[1][4]) 1。不相等f[2][4] f[1][4] 0。j 5B[5] 4不大于 3不相等f[2][5] f[1][5] 0。j 6B[6] 5不大于 3不相等f[2][6] f[1][6] 0。i 3A[3] 1。这一轮比较特殊因为 A[3] 1 是当前最小的数。所有 B[j] 都大于等于 1所以 maxv 一直保持 0。B[4] 2 ! 1B[3] 3 ! 1……没有一个 B[j] 等于 1B 中没有 1所以这行所有的 f[3][j] 都等于 f[2][j]。i 4A[4] 4。j 1B[1] 1 4maxv max(0, f[3][1]) 0。不相等f[4][1] 0。j 2B[2] 2 4maxv max(0, f[3][2]) 1。不相等f[4][2] 1。j 3B[3] 3 4maxv max(1, f[3][3]) 2。不相等f[4][3] 2。j 4B[4] 2 4maxv max(2, f[3][4]) 2。不相等f[4][4] 0。j 5B[5] 4不大于 4maxv 2。B[5] A[4] 成立f[4][5] maxv 1 3。这里构造出的 LCIS 是 [1? 不对是 [2, 3, 4] 吗注意f[3][3] 2 表示 A 的前 3 个元素、B 的前 3 个元素中以 B[3] 3 结尾的 LCIS 是 [2, 3]。现在 A[4] 4B[5] 4二者相等而前面的 maxv 2 表示存在长度为 2 且末尾小于 4 的公共上升子序列即 [2, 3]接上 4 得到 [2, 3, 4]长度 3。j 6B[6] 5不大于 4不相等f[4][6] f[3][6] 0。i 5A[5] 2。j 1B[1] 1 2maxv 0。不相等f[5][1] 0。j 2B[2] 2不大于 2maxv 0。B[2] A[5]f[5][2] maxv 1 1。j 3B[3] 3不小于 2maxv 0。不相等f[5][3] f[4][3] 2。j 4B[4] 2不大于 2maxv 0。B[4] A[5]f[5][4] maxv 1 1。j 5B[5] 4不小于 2maxv 0。不相等f[5][5] f[4][5] 3。j 6B[6] 5不小于 2maxv 0。不相等f[5][6] f[4][6] 0。i 6A[6] 5。j 1B[1] 1 5maxv max(0, f[5][1]) 0。j 2B[2] 2 5maxv max(0, f[5][2]) 1。j 3B[3] 3 5maxv max(1, f[5][3]) 2。j 4B[4] 2 5maxv max(2, f[5][4]) 2。j 5B[5] 4 5maxv max(2, f[5][5]) 3。j 6B[6] 5不大于 5maxv 3。B[6] A[6]f[6][6] maxv 1 4。最终答案取所有 f[i][j] 的最大值max(f[6][j]) 4对应 [2, 3, 4, 5]。模拟结果正确。这个模拟过程有几个值得注意的点在 i 5 那一行f[5][4] 1但它没有影响最终答案因为以 B[4] 2 结尾的序列长度天然会被以 B[2] 2 结尾的序列取代都是 2但更早出现的位置保留了更多后续扩展空间。这就是为什么用“以 B[j] 结尾”而不是“以 A[i] 结尾”——B 中的位置信息天然保留了顺序约束。需要注意 j 4 这一点B[4] 2它在模拟中扮演了“干扰项”的角色。由于 B 中 2 出现了两次程序能正确处理两种情况第一次出现j2时作为新的候选加入第二次出现j4也不影响 maxv因为 maxv 要求严格小于 A[i]2 不小于 2。这说明 DP 自动规避了重复使用相同元素的问题。如果你在本地手动推演了几行之后发现自己的表跟上面的结果不一致多数情况出现在 maxv 的更新时机上。要么是提前把等于 A[i] 的 B[j] 计入了 maxv导致后面重复拼接要么是太晚更新导致漏掉了当前 j 之前的候选。这里建议把“更新 maxv”和“计算 f[i][j]”看成两个独立的步骤先看 B[j] 能不能作为“前驱”B[j] A[i]再看 B[j] 能不能作为“终点”B[j] A[i]。一个位置完全可以既是前驱又是终点吗不行因为严格递增要求前驱必须小于终点二者不能相等。所以上面例子中 j 2 处B[2] 2 不能作为 A[1] 2 的前驱但可以作为终点。这一点在写代码时是天然判别的。5. 代码实现与常见问题排查5.1 可运行的 C 实现下面给出一个完整可运行的 C 版本包含输入输出和注释。很多在线评测题目只需要输出长度这个实现直接返回长度即可。如果题目要求输出具体序列我会在第 6 节补充方案。#include bits/stdc.h using namespace std; const int N 1005; int a[N], b[N]; int f[N][N]; int main() { int n, m; scanf(%d, n); for (int i 1; i n; i) scanf(%d, a[i]); scanf(%d, m); for (int j 1; j m; j) scanf(%d, b[j]); int ans 0; for (int i 1; i n; i) { int maxv 0; for (int j 1; j m; j) { if (b[j] a[i]) { maxv max(maxv, f[i - 1][j]); } f[i][j] f[i - 1][j]; // 先继承 if (a[i] b[j]) { f[i][j] max(f[i][j], maxv 1); } ans max(ans, f[i][j]); } } printf(%d\n, ans); return 0; }这段代码的时间复杂度 O(nm)空间复杂度 O(nm)。对于 n, m 1000 的题完全可以跑如果 n, m 都到 5000O(2500 万) 也勉强可以再大就需要考虑滚动数组优化空间了。5.2 空间优化到 O(m)注意到状态转移中f[i] 这一行只依赖 f[i-1] 这一行所以可以把第一维滚掉。但有个细节maxv 在每一轮 i 都要重新初始化为 0因为它是针对当前 A[i] 来统计前驱长度的。优化后的代码如下#include bits/stdc.h using namespace std; const int N 1005; int a[N], b[N]; int f[N]; // 滚动数组f[j] 表示当前 i 下以 B[j] 结尾的 LCIS 长度 int main() { int n, m; scanf(%d, n); for (int i 1; i n; i) scanf(%d, a[i]); scanf(%d, m); for (int j 1; j m; j) scanf(%d, b[j]); int ans 0; for (int i 1; i n; i) { int maxv 0; for (int j 1; j m; j) { if (b[j] a[i]) { maxv max(maxv, f[j]); } if (a[i] b[j]) { f[j] max(f[j], maxv 1); } ans max(ans, f[j]); } } printf(%d\n, ans); return 0; }注意滚动数组版本里f[j] 在更新时有一个 max(f[j], maxv 1) 的保护。为什么要加 max因为在同一轮 i 中f[j] 可能已经在上一轮 i-1 中有了一个非零值而 maxv 1 可能更小。举个例子f[j] 之前是 5但当前 i 对应的 maxv 只有 2那 3 比 5 小不该覆盖。滚动数组最大的坑就在这里——不小心覆盖了上一轮的长答案。做了空间优化后代码本身依然可以直接输出最长长度。但如果题目要求输出方案滚动数组会丢失路径信息所以输出方案版建议保留二维数组。下面讨论输出方案。5.3 如何输出最长公共上升子序列本身输出方案的关键是回溯。在二维数组的版本上增加一个 pre[i][j]记录 f[i][j] 是从哪个状态转移过来的。当 f[i][j] maxv 1 时意味着它把“以某个 B[k] 结尾的长度为 maxv 的序列”接上了 B[j] 这个新元素所以需要记录上一次的 k。具体做法在外层循环内维护 maxv 的同时也记录产生 maxv 的位置 pre_k。当用 maxv 1 更新 f[i][j] 时pre[i][j] pre_k。回溯时从终点最优值对应的 i, j不断往前跳最后倒序输出 B 中的对应元素。#include bits/stdc.h using namespace std; const int N 1005; int a[N], b[N]; int f[N][N]; int pre[N][N]; // 记录 f[i][j] 的前驱位置 int main() { int n, m; scanf(%d, n); for (int i 1; i n; i) scanf(%d, a[i]); scanf(%d, m); for (int j 1; j m; j) scanf(%d, b[j]); int ans 0, ans_i 0, ans_j 0; for (int i 1; i n; i) { int maxv 0; int pre_k 0; // 产生 maxv 的位置 for (int j 1; j m; j) { f[i][j] f[i - 1][j]; pre[i][j] -1; // 默认无前驱 if (b[j] a[i] f[i - 1][j] maxv) { maxv f[i - 1][j]; pre_k j; } if (a[i] b[j] maxv 1 f[i][j]) { f[i][j] maxv 1; pre[i][j] pre_k; // 记录前驱位置 } if (f[i][j] ans) { ans f[i][j]; ans_i i; ans_j j; } } } printf(%d\n, ans); if (ans 0) { vectorint seq; int ii ans_i, jj ans_j; while (jj 0) { if (ii 0 || pre[ii][jj] -1) { // 如果当前状态没有前驱说明这段序列起点就是当前 jj 对应的 B[jj] if (ans 0) { seq.push_back(b[jj]); ans--; } break; } // 只有当 f[ii][jj] 大于 f[ii-1][jj] 时说明当前位置是新增的元素 if (f[ii][jj] ! f[ii - 1][jj]) { seq.push_back(b[jj]); jj pre[ii][jj]; ii--; } else { ii--; // 往上继承不添加元素 } } reverse(seq.begin(), seq.end()); for (int x : seq) printf(%d , x); printf(\n); } return 0; }回溯部分的逻辑容易出错我建议你重点理解“何时添加元素”和“何时只是继承”——只有当 f[i][j] 比 f[i-1][j] 大的时候说明 B[j] 在当前 i 下被选中作为新元素否则就是单纯地继承上一行的状态这时候只移动 i不往序列里加东西。5.4 常见错误与排查对照表我整理了这份实现中容易踩的坑每条都是真实出现过的问题错误现象可能原因排查方法答案偏小maxv 更新时机错误漏掉了部分候选在本地打印每轮 i 的 maxv 变化检查是否包含 b[j] a[i] 的全部候选答案偏大非严格递增把 b[j] a[i] 写成了 b[j] a[i]检查比较符号严格递增必须用 答案变成 LCS 长度没有维护“上升”条件把 maxv 当成全局最大值确认 maxv 只在 b[j] a[i] 时更新滚动数组版答案错误更新 f[j] 时没有取 max覆盖了上一轮的更长序列检查更新语句是否写成 f[j] max(f[j], maxv 1)多组数据未清空数组f 数组残留上一组数据在每组数据前 memset(f, 0, sizeof(f))输出方案时死循环回溯逻辑中 jj 没有正确跳转在 while 循环中打印 jj 和 pre[ii][jj] 调试额外的排错技巧小规模数据n, m 8时可以用暴力枚举法验证答案。暴力代码不复杂枚举 A 的所有子序列判断是否递增且是 B 的子序列取最大长度。用这个对拍器验证 DP 答案能快速定位是状态定义问题还是实现细节问题。这个方法我在学 DP 阶段屡试不爽强烈建议你也保留一个暴力对拍模板。6. 状态划分的思维模型为什么这道题值得反复琢磨6.1 “以谁结尾”的选择决定了维度和复杂度很多人学 DP 喜欢背模板但 LCIS 问题的价值恰恰在于它逼着你理解“状态划分”这件事。LIS 用“以 i 结尾”LCS 用“前缀 i,j”LCIS 需要把两者的思想融合成“前缀 i,j 且以 B[j] 结尾”。这个“且”字就是状态划分的精髓——它把额外的约束条件直接揉进状态维度里避免在转移时额外比较从而实现 O(n*m) 的复杂度。我自己的体会是遇到一个陌生的 DP 题不要急着套模板先想清楚这样几个问题什么样的信息会影响到后续的决策在 LCIS 中是当前子序列的末尾值这个信息能不能直接放进状态里末尾值放进状态代价是增加一维但用“以 B[j] 结尾”的方式并入已有的 j 维度就不增加额外维度转移时能否用“前缀扫描”的思路把内层循环优化成维护一个变量只要顺着这三步走很多看起来无从下手的题都能找到突破口。LCIS 是最经典的教学案例因为它把每一步都展现得很清晰先确定状态维度再推导转移最后发现可以滚动优化。这条思路链完整、可复现所以特别适合作为训练自己 DP 思维的工具。6.2 与 LIS、LCS 的横向对比把三个模型放在一张表里对比能更清楚地看出各自的设计考量模型状态定义状态维度时间复杂度核心思想LISdp[i] 表示以 A[i] 结尾的 LIS 长度1 维O(n log n) 或 O(n^2)维护前缀最小值LCSdp[i][j] 表示 A 前 i 个和 B 前 j 个的 LCS 长度2 维O(n*m)前缀匹配分类讨论LCISdp[i][j] 表示 A 前 i 个、B 前 j 个且以 B[j] 结尾的 LCIS 长度2 维O(n*m)融合“结尾元素”和“前缀匹配”从表中能看出LCIS 在状态维度上吸收了 LCS 的二维结构在转移方式上借用了 LIS 的“以某个元素结尾”思想同时引入 maxv 变量来压缩扫描成本。它并不是 LIS 和 LCS 的简单叠加而是二者在更高维度上的融合。6.3 变体与扩展思路LCIS 还有一些常见变体理解原题后可以轻松迁移非严格递增 LCIS把 b[j] a[i] 改成 b[j] a[i] 即可但输出方案时要注意可能存在的重复元素。最长公共下降子序列LCDS把小于号改成大于号思路完全对称。三序列 LCIS给出 A、B、C 三个序列求三者的公共上升子序列。状态需要扩展为 dp[i][j][k]复杂度随之变为 O(nml)。这个变体在实践中较少见但能检验你是否真正理解状态设计。带权 LCIS每个元素有一个权值求权值和最大的公共上升子序列。转移时将1改为w[j]或w[i]maxv 维护的是最大权值和而不是长度。这些变体在面试或竞赛中偶尔出现核心思路不变关键是能把原题的“为什么”讲清楚变体就只是改条件而已。7. 实测经验与性能对比我本地用随机生成的大数据跑了一下三种实现的耗时n m 1000朴素 O(nmm) 版本约 1.2 秒在 O2 优化下。O(n*m) 版本约 0.008 秒。O(n*m) 滚动数组版本约 0.007 秒内存占用从 4MB 降到 4KB。如果 n m 5000朴素版本已经无法在合理时间内跑完约 1250 亿次操作而 O(nm) 版本大约 0.2 秒滚动数组版本内存优势更明显。所以在实际比赛或笔试中强烈建议直接用 O(nm) 的滚动数组版本既省心又高效。另外一个性能细节如果 n 和 m 明显不等比如 n 1e5, m 1e3直接跑 O(n*m) 可能超时。这时候可以判断一下如果某个序列里出现的元素在另一个序列中完全没有可以先做一次“预筛选”把两边都出现过的元素保留下来。这是一个很实用的优化技巧做数据预处理时能显著减少规模。我实际测试过这样一个场景A 长度 100000B 长度 1000但 B 中有一半的元素在 A 中不存在。预筛选后A 的有效长度降到约 50000B 的有效长度降到 500复杂度从 1e8 降到 2.5e7跑起来明显更快。8. 这类题该怎么刷从 LCIS 到进阶 DP 的路径建议学完 LCIS 之后可以在它基础上延伸出很多变体题比如最大公共子序列和、公共递增子序列数量等。但这里我更想强调的是一条学习路径不要只盯着 LCIS 的代码要把它当作“状态划分”的典型病例来解剖。具体来说刷 DP 题时建议坚持三步走第一步先写暴力 DFS 或记忆化搜索版本理清状态和转移。LCIS 的记忆化搜索版本很好写就是枚举 i 和 j 以及可能的 k比直接写递推更容易理解。第二步把记忆化搜索改成递推并尝试用滚动变量优化。这个过程中你会真正体会到“为什么要维护 maxv”——因为它在递推顺序上恰好能复用而记忆化搜索里这个优化往往不明显。第三步在草稿纸上画出状态表、标出转移路径尝试输出一个完整方案。这一步是检验是否真正理解的最好方式因为输出方案需要你回溯每一条转移边比只求最值难得多。我见过很多同学刷了 50 道 DP 题但问他“为什么这个状态要这么定义”却答不上来。这种状态很危险——遇到稍微变形的题目就无从下手。LCIS 作为经典中的经典正好可以拿来检验自己是否具备“设计状态”的能力而不是只会抄模板。最后分享一个我的个人习惯每学完一个新模型我都会尝试把它和至少一个已学模型对比在笔记里画一张“模型关系图”。比如 LIS 和 LCS 如何融合成 LCISLCIS 如何退化成一维 LIS当 B 是排序数组时或退化成 LCS当所有元素等值时。这种对比让知识形成网络而不是孤立的知识点。刷题时遇到新题先在脑子里过一遍这个网络看看它属于哪个节点的变体往往很快就有思路了。