最近刷题刷到一道很经典的线性dp题目——最长公共上升子序列Longest Common Increasing Subsequence简称LCIS。这题在算法圈子里地位挺高因为它把最长上升子序列LIS和最长公共子序列LCS两个经典模型揉在了一起现场推状态转移的时候很容易卡壳。尤其是状态划分这一步看似简单但对“以谁结尾”“属性是什么”的理解稍微差一点后面代码就写不顺。这篇东西我打算按自己做题时的思考路径来写先从两个母题的思路切入解释清楚为什么LCIS的状态不能直接套LCS再带着你做一次完整的集合划分推导最后给出O(n²)的可直接AC代码和打印路径的扩展。适合刚学完LIS和LCS、想在动态规划上再往上走一步的同学老手也可以重点看第3节的优化trick和第5节的路径回溯权当复习一下状态设计的感觉。1. 问题本质为什么说它是两个模型的“组合题”1.1 先理清两个“母题”各自的状态设计要理解LCIS先回忆两个基础模型的状态长什么样。最长上升子序列LIS核心状态是f[i]表示“以a[i]结尾的最长上升子序列长度”。转移时枚举i之前的所有位置j只要a[j] a[i]就可以从f[j] 1转移过来。这个过程有一个贪心加二分优化版本能做到O(nlogn)但状态本身的含义是不变的——以某个元素结尾。最长公共子序列LCS核心状态是f[i][j]表示“a的前i个字符和b的前j个字符的最长公共子序列长度”。转移就两个方向a[i] b[j]时f[i][j] f[i-1][j-1] 1否则在f[i-1][j]和f[i][j-1]里取max。这个模型的精髓在于“前缀视角”所有状态都挂在两个序列的前缀上不关心具体以哪个字符结尾。LCIS这题要求的子序列有三个性质来自公共部分、保持两个序列各自的下标递增、数值严格递增。前两个性质是LCS的范畴最后一个性质是LIS的范畴。于是问题来了你应该用“前缀”来定义状态还是用“结尾元素”来定义状态我在第一次做题时第一反应是照搬LCS的f[i][j]只在a[i] b[j]的时候尝试做一些上升判断结果写出来的转移又臭又长还容易漏状态。后来看了一些题解才发现这类“既要公共又要单调”的题状态设计的关键不是像谁而是看你最后能不能用一个清晰的“集合划分”讲清楚每个状态怎么来。1.2 LCIS的难点到底卡在哪里把三个模型放一起对比可以看得更清楚模型状态定义状态数量转移复杂度核心思想LISf[i]以a[i]结尾的LIS长度O(n)O(n²)可优化O(nlogn)以结尾元素定位状态LCSf[i][j]a前i个与b前j个的LCS长度O(n²)O(n²)前缀视角递推LCISf[i][j]a前i个与b前j个中以b[j]结尾的LCIS长度O(n²)O(n²)前缀 结尾元素双重视角注意LCIS这行的状态定义我写的是“a前i个与b前j个中以b[j]结尾”。这是理解整道题最关键的一句话。为什么不能是“以a[i]结尾”因为公共子序列要同时出现在两个序列里如果你固定的是a[i]结尾那么在b里找对应元素时还要额外判断相等关系状态转移会变得非常纠结而固定b[j]结尾再配合a的前缀i做扫描就能在枚举过程中天然处理“相等才更新”这个条件。所以状态的定义必须回答三个问题扫描范围是什么a取了前i个b取了前j个结尾元素是谁以b[j]结尾维护的属性是什么最长序列长度这种把“范围 结尾”组合在一起定义状态的方式就是线性dp里常说的“状态划分”。LCIS这道题本质上是在训练你如何为了让转移清晰去重新设计状态。2. 状态定义与状态划分的核心思路2.1 固定“以b[j]结尾”再枚举a的前缀正式定义状态f[i][j]表示“在a[1..i]和b[1..j]中所有公共上升子序列里以b[j]结尾的那一类长度最大值”。这里有个容易忽略的小细节既然是以b[j]结尾那么这个子序列里一定包含b[j]。又因为它是公共子序列所以b[j]这个值也一定出现在a[1..i]中的某个位置。也就是说如果a[i]不等于b[j]那f[i][j]和f[i-1][j]是等价的因为你把a[i]纳入不考虑也不会影响“以b[j]结尾”这件事。于是就有了LCS风格的转移骨架当a[i] ! b[j]时f[i][j] f[i-1][j]当a[i] b[j]时可以在f[i-1][j]的基础上再考虑把a[i]也就是b[j]接到某个前面已经形成的上升子序列后面长度加1。后面这种“接上去”的操作就需要LIS风格的转移了——往前找一个比当前结尾元素更小的“前驱结尾”。2.2 集合划分的两种常用方案把这层逻辑用集合划分的语言说清楚是所有题解都会做的事但很多题解直接扔结论没讲为什么这么划。我当时自己推了一遍发现两种划分方式其实都能做只是代码写法差很多。方案一按“最后一个来源位置”划分。对于f[i][j]如果a[i] b[j]枚举位置k1 k j看有没有b[k] b[j]的f[i-1][k]如果有就可以把b[j]接到b[k]的后面。这样转移是f[i][j] max(f[i-1][j], max_{1kj且b[k]b[j]} (f[i-1][k] 1))这个写法直接、好懂但代价是三层循环复杂度O(n³)。方案二等价但更优雅在枚举k的过程中动态维护一个最大值变量。因为随着i固定j从左往右扫你其实可以一边扫一边更新“当前满足b[k] b[j]的f[i-1][k]最大值”把对k的枚举从内层循环中“提”出来。这就是经典的O(n²)优化具体细节放到第3节。两种方案本质上是同一套集合划分区别在于方案二把方案一里重复计算的max结果用滚动变量保存下来避免了每次重新枚举。这就是很多解法里说的“前缀最大值优化”名字听起来高大上实际就是省了一次重复循环。3. 三步走从朴素O(n³)优化到O(n²)3.1 先写朴素版本确保逻辑正确我一般做题的习惯是先写一版能保证正确的朴素代码再考虑优化。这样即使后来优化错了手里也还有一版对照。这个朴素版本直接把状态定义和集合划分翻译成代码#include iostream using namespace std; const int N 3005; int a[N], b[N]; int f[N][N]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) cin b[i]; for (int i 1; i n; i) { for (int j 1; j n; j) { f[i][j] f[i - 1][j]; if (a[i] b[j]) { int maxv 0; for (int k 1; k j; k) { if (b[k] b[j]) maxv max(maxv, f[i - 1][k]); } f[i][j] max(f[i][j], maxv 1); } } } int ans 0; for (int j 1; j n; j) ans max(ans, f[n][j]); cout ans endl; return 0; }为什么答案要取f[n][j]的最大值因为公共上升子序列并不要求一定以哪个位置结尾可能a[n]和b[j]完全不相等所以必须在所有f[n][j]里取max。这个细节很多人写代码时忘了结果样例能过一到大数据就莫名其妙少1。这套代码的时间复杂度是O(n³)n在1000左右还能勉强跑到了3000就直接超时。不过逻辑很清晰适合拿来做对拍验证。3.2 优化trick用滚动变量维护“前缀最大值”现在做优化。观察朴素版本的内层循环for (int k 1; k j; k) { if (b[k] b[j]) maxv max(maxv, f[i - 1][k]); }这个循环做的事情就是在b[1..j-1]里找出所有值小于b[j]的位置k取f[i-1][k]的最大值。仔细看这个最大值是随着j的增大可以递推维护的。假设我们用变量maxv表示“当外层i固定时在已经扫过的b[1..j-1]中所有满足b[k] b[j]的f[i-1][k]的最大值”。那么每次j从1扫到n的过程中我们可以提前维护一个“全局当前最优”的值cur每当处理完一个j后发现b[j] b[未来的某值]时f[i-1][j]就可能成为未来的候选所以我们在窗口右移的过程中维护“当前已经扫过的所有位置里值小于当前b[j]的f最大值”。更具体的写法是在遍历j之前初始化cur 0当a[i] b[j]时更新cur max(cur, f[i-1][j])。你要注意这里比较的是a[i] b[j]而不是b[k] b[j]为什么因为我们在内层循环里判断的是b[k] b[j]而外层循环固定了a[i]只有当a[i] b[j]时才会真正用到cur。为了让cur代表“所有值小于a[i]的b[k]对应的f最大值”我们在扫描j时只要发现b[j] a[i]就说明b[j]可以作为未来以a[i]结尾的序列的前驱候选于是用f[i-1][j]更新cur。这样一来等到a[i] b[j]的时候cur已经自动维护好了直接取cur 1就行。3.3 最终一维滚动数组实现状态转移时f[i][j]只依赖f[i-1][j]和f[i-1][k]都是上一轮i-1的结果所以可以去掉第一维只保留一维数组f[j]。但这有个小陷阱如果直接原地更新f[j]可能会被本轮i覆盖影响后面j的判断。好在我们的转移逻辑里用到f[j]的地方有两类a[i] ! b[j]时f[j]保持不变继承上一轮结果a[i] b[j]时f[j] max(f[j], cur 1)其中cur是在本轮已经更新过的变量只依赖上一轮的f[k]不依赖本轮被覆盖后的f[k]。于是滚动数组是安全的。完整代码如下#include iostream #include algorithm using namespace std; const int N 3005; int a[N], b[N]; int f[N]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) cin b[i]; for (int i 1; i n; i) { int cur 0; for (int j 1; j n; j) { if (a[i] b[j]) { f[j] max(f[j], cur 1); } if (b[j] a[i]) { cur max(cur, f[j]); } } } int ans 0; for (int j 1; j n; j) ans max(ans, f[j]); cout ans endl; return 0; }这里有几处顺序非常讲究进入内层循环时cur必须为0代表“还没有找到任何可以作为前驱的元素”。之后每遇到一个b[j] a[i]就用f[j]更新cur表示“这个位置可以作为未来某个以a[i]结尾的子序列的前驱”。先判断a[i] b[j]并更新f[j]再判断b[j] a[i]并更新cur。如果把顺序反了当a[i] b[j]时b[j] a[i]为假不会影响cur但有一种情况要注意如果a[i] b[j]且b[j]本身又和某个a[i]相等f[j]在同一轮里被更新后cur用更新后的f[j]继续往后传这其实是有问题的。因为f[i][j]本来应该用上一轮的f[i-1][j]来更新cur而不是本轮f[i][j]。好在我们的更新顺序是先处理相等情况再处理b[j] a[i]所以当b[j] a[i]时如果a[i] b[j]为假f[j]没有被本轮修改依然是上一轮的值安全。如果相等为真那么b[j] a[i]为假不会进入更新cur分支也不会出错。这块逻辑虽然容易绕晕但理解之后就会觉得这个顺序设计得非常精妙。循环结束后f数组中每个位置的含义是“以b[j]结尾的当前最长公共上升子序列长度”注意这里并不区分a的前缀到哪里因为滚动数组已经把i的维度压缩掉了最终读到的就是处理完整个a数组后的结果。我测试过这版代码在n3000的数量级下运行时间大概是十几毫秒放竞赛里也完全没有压力。对比朴素版本的秒级超时这个优化立竿见影。4. 代码细节与边界处理4.1 初始化为什么全部为0而不是负无穷有些dp问题要求初始化为负无穷比如求恰好装满的背包问题。这里不需要因为空的公共上升子序列是合法方案长度为0它对应着“什么都还没选”的状态。f数组初始全0其实就表示“在a的前0个元素和b的前j个元素中以b[j]结尾的LCIS长度为0”——虽然b[j]根本不在a里但长度为0的空序列总存在不影响正确性。等后续i递增时f[j]会被逐步更新成真正的长度。这也是一个通用的判断标准如果状态允许“空方案”且题目求的是最大值初始化为0通常没问题。只有要求恰好某种条件时才考虑负无穷。4.2 为什么答案要取max而不是f[n]很多新手看到f[i][j]定义里的“以b[j]结尾”就觉得最后答案应该是f[n][n]。但f[n][n]表示的是“以b[n]结尾的最长公共上升子序列”LCIS不一定非要以b的最后一个元素结尾。比如a和b分别是{1, 3, 2}和{1, 2}最长公共上升子序列是{1, 2}长度为2但它不以b[3]结尾因为b[3]不存在序列就截止在b[2]了。所以必须对所有j取max。4.3 关于“上升”是严格还是非严格题目一般说“上升”默认是严格递增也就是b[k] b[j]代码里对应b[j] a[i]。如果题目改成“非严格上升”只要把换成即可但要注意这样可能会引入连续相同元素的序列需要重新验证状态转移的边界。还有一个小点如果a和b里有重复元素严格上升条件下同一个值不可能被选两次。比如a是{2, 2}b是{2}LCIS长度是1而不是2。如果你的代码写的是就会错误地得到2。这个我在对拍时就踩过坑所以默认情况下一定用严格小于。4.4 关于数组长度和数据范围题目里n的上限常见值是3000此时二维数组f[3005][3005]是约900万个int内存约36MB勉强能过。如果n到5000甚至更大就必须用滚动数组。所以上面给出的最终代码直接用一维内存只占约12KB毫无压力。另外输入数据如果从0开始存代码里循环下标要从0而不是1开始对应的转移逻辑也要整体往左移一位。我个人习惯从1开始存这样f[j]和b[j]的下标一一对应不容易把下标搞混。这属于个人风格但建议初学者统一用一种别在刷题时换来换去。5. 进阶打印出完整的最长公共上升子序列竞赛里很多时候只需要输出长度但面试或实际场景中考官可能会追问“能不能把序列本身打出来”。这就需要额外记录转移路径。原理和LCS打印路径类似开一个pre[j]数组记录“以b[j]结尾的LCIS它的前一个元素在b中的位置”。当a[i] b[j]且cur 1 f[j]时说明当前以b[j]结尾的新长度来自某个位置p这个p就是维护cur时记录下来的最优前驱位置。实现时需要在维护cur的同时也记录cur对应的下标#include iostream #include algorithm #include vector using namespace std; const int N 3005; int a[N], b[N]; int f[N], pre[N]; int main() { int n; cin n; for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) cin b[i]; for (int i 1; i n; i) { int cur 0, curPos 0; for (int j 1; j n; j) { if (a[i] b[j]) { if (cur 1 f[j]) { f[j] cur 1; pre[j] curPos; } } if (b[j] a[i]) { if (f[j] cur) { cur f[j]; curPos j; } } } } int ans 0, endPos 0; for (int j 1; j n; j) { if (f[j] ans) { ans f[j]; endPos j; } } vectorint path; while (endPos) { path.push_back(b[endPos]); endPos pre[endPos]; } reverse(path.begin(), path.end()); cout ans endl; for (int x : path) cout x ; cout endl; return 0; }这段代码里要注意的点curPos必须和cur同步更新不能只更新值不更新下标。另外pre数组在执行过程中会被覆盖但由于我们只需要最终路径而不是每一轮的完整路径所以数组覆盖不影响最终结果。这个逻辑和LIS里记录g[i]来回溯的思路一脉相承。如果题目有多组测试数据记得在每组数据前把f和pre清零否则上一次的残留值会导致状态错误。我写代码时曾经因为忘了清pre导致路径里出现一堆诡异的下标排查了半天才发现是初始化问题。6. 常见问题与避坑技巧做题多了之后我把LCIS相关的坑整理成一张表每次写代码前都会快速过一遍问题现象可能原因解决办法答案总是比标准答案小1忘掉“以任意b[j]结尾”取最大直接输出f[n][n]答案用max遍历所有f[j]O(n³)版本超时内层k循环重复计算用cur变量维护前缀最大值降到O(n²)输出序列有重复元素把小于写成小于等于严格上升用非严格才用多组数据结果相互污染f数组未清零每组数据前fill或memset滚动数组顺序错了结果乱跳先判断a[i]b[j]和先更新cur的顺序搞反保持“先判断相等再判断小于”的顺序打印路径为空pre数组初始化为0回溯时没进入循环检查endPos是否为正以及pre是否被正确记录输入下标从0开始导致转移错位循环边界和数组定义不一致统一下标风格推荐从1开始除了表格里的坑再分享几个实际的调试心得第一遇到答案不对的情况先用小规模数据手动对拍。把n设为5以内分别打印朴素版和优化版的f数组比对差异。很多时候误差出现在某一轮cur的更新顺序上肉眼对比数组就能定位。第二可以用随机数据生成器写一个暴力O(n³)版配合O(n²)版做对拍。暴力版代码简单、逻辑直观是最可靠的“标准答案”。生成随机数组时注意数值范围不能太小否则重复元素太多上升判断容易出歧义。第三关于时间复杂度的选择n在1000以内时O(n³)大概几千万次运算也就几十毫秒直接交了不会有问题n到了3000以上O(n³)是27亿次运算必超时。所以优化版是必会的不能只会朴素写法。第四有一个思维方式上的坑值得强调。很多人包括我最初在内都试图给LCIS套LIS的“贪心 二分”优化。这里要提醒一下LCIS的公共性导致你不能简单地对b维护一个单调栈因为每一个上升子序列还必须保证公共约束贪心策略很难同时满足两个维度。所以常规解法就是O(n²)不要浪费时间想什么“nlogn解法”。少数论文里有优化到近似O(nlogn)的做法但实现复杂且适用性有限竞赛里O(n²)完全够用。7. 从LCIS到更多线性dp模型的迁移学完LCIS后你可以再回头看看LIS和LCS体会一下“状态定义”这个敲门砖到底有多重要。很多题看起来复杂其实都是这两个模型的变形组合最长公共子序列 计数多维护一个数组记录方案数最长上升子序列 字典序最小贪心选择最早可行位置最长公共上升子序列 路径记录本节已经做了本质就是在转移时记录前驱两个序列的LCIS扩展到k个序列多维版本状态设计思路一致只是维度增加。这类“模型拼接”题在面试和算法竞赛里都很常见。套路就是先把两个母题的状态定义吃透再针对新题目加一个限制条件看看状态里需要增加什么维度、转移时需要增加什么判断。LCIS刚好是最好的练手材料因为它同时涉及“前缀”和“结尾元素”两种视角逼着你把集合划分想清楚。我个人刷题时的体会是LCIS这道题不要背代码要能在一张白纸上从状态定义开始推出来。推一遍比看十遍题解都管用。每推一次你对“为什么固定b[j]而不是a[i]”“为什么cur要在内层循环里维护”这些细节的理解就会深一截。等你哪天闭着眼睛都能画出转移图了再遇到“最长xx子序列”的变种题思路就会非常顺畅。最后再分享一个小技巧如果面试官让你写LCIS可以先说出状态定义和集合划分逻辑再写代码。因为大部分面试官更在意你的思考过程而不是代码默写能力。代码写完之后主动补一句“这里用滚动数组优化了空间复杂度原来的二维f简化为一维”这个细节特别加分能直接体现你对dp优化的熟练度。