序列问题模型这个东西越早拆透越好。我自己带过不少刚入行的人最常见的面试翻车场景基本长这样面试官抛出一道最长递增子序列的变形题让你先说思路再写代码写完之后又追一句数组长度到10^5你的O(n^2)还能过吗。没系统啃过LIS、LCS、LCIS这三个模型的听到动态规划四个字先点头真到写状态定义的时候就开始乱套——dp数组到底开几维、转移方向是从前到后还是从后到前、最后答案是dp[n]还是max(dp[i])全凭感觉猜。这篇文章把LIS、LCS、LCIS一次性讲透从状态定义、转移方程推导、空间优化到序列回溯重建再到三者在真实面试题里的综合变形适合正在备战算法岗面试、刷LeetCode卡在序列类题目、或者打ACM想补齐基础DP模型的读者。看完之后你会发现这三个模型其实共享一套骨架真正要弄清楚的就那么几个关键点。1. 为什么序列问题模型值得花时间拆透1.1 序列问题的真实应用场景远比想象中广很多人以为LIS、LCS、LCIS是纯竞赛玩具题面试考到只是用来筛人。其实这三个模型在工程里的映射非常直接。LIS对应的是一维趋势分析比如K线里统计最长连续一段保持上涨的区间、时间序列里找最长单调递增的时间段、甚至游戏排行榜里判断玩家最好成绩曲线的上升空间。LCS对应的是找两个序列的最长共同片断基因序列比对、diff工具里计算两个版本的共同部分、代码查重系统里判断两个文件是否抄袭、搜索推荐里衡量用户行为序列的相似度。LCIS则是更高一档的要求既要共同又要递增典型场景是匹配两份日志序列里最长的共同增长趋势、或者判断两个版本的数据变更列表里最长的同步演进片段。理解了这些场景再看面试题就不会觉得它们在刁难人而是在检验你有没有把经典模型的本质吃透。1.2 三种模型共享的DP骨架我第一次学DP的时候最大的困惑是每个题目的状态定义都不一样记不住。后来把LIS、LCS、LCIS放在一起对比才意识到它们骨子里是同一件事在一个或两个序列上做顺序扫描每一步决定当前位置选不选进结果序列然后用一个数组记录以某个位置为结尾时的最优值。LIS是单序列选子序列LCS是双序列选共同子序列LCIS是双序列选共同且递增的子序列。三者都是一维或二维的线性DP转移都依赖上一个被选择的位置区别只在于约束条件不一样。把这三个放在一起学比一个一个孤立地背效率高得多。1.3 学习顺序与预期我的建议是先啃LIS它是最简单的单序列模型能帮你理解以i结尾这种状态定义的价值。再学LCS它把状态扩展到二维同时带来空间优化的典型套路。最后再看LCIS它是在LCS的骨架上叠加了递增约束核心优化技巧是从O(n^3)降到O(n^2)的过程这一步能让你真正理解DP优化的思维方式。这篇文章会完全按照这个顺序展开每个模型都附上可直接运行的代码和手算推演的样例方便你边读边验证。2. LIS最长递增子序列从O(n^2)到O(n log n)两种境界2.1 O(n^2)解法状态定义和转移方程是怎么来的先明确LIS的定义在数组a中选出一个子序列保持原来的相对顺序每个元素严格大于前一个求能选出的最大长度。注意子序列不是子串中间可以跳元素这是很多人一开始会犯迷糊的点。定义dp[i]表示以a[i]作为最后一个元素的最长递增子序列长度。为什么要刻意加上以a[i]结尾因为只有知道结尾是谁才能判断能不能在后面续一个新的更大的元素。如果状态定义为前i个元素的最长递增子序列长度转移时你会丢失结尾信息没法判断a[j]能不能接在末尾。这是DP状态设计最关键的一课状态要保留转移所需的全部信息。转移方程一句话dp[i] max(dp[j] 1)其中j i且a[j] a[i]。同时每个元素自身可以单独成一个子序列所以dp[i]至少是1。代码很短int lisOn2(vectorint a) { int n a.size(); vectorint dp(n, 1); int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }注意最后答案是dp数组里的最大值不是dp[n-1]。因为最长递增子序列不一定以最后一个元素结尾。这是我带人时常提醒的一句很多人习惯性地返回最后一位正好掉进陷阱里。2.2 O(n log n)解法贪心加二分的本质当n达到10^5甚至10^6O(n^2)就不行了。优化思路很经典维护一个数组dd[len]表示长度为len的递增子序列中最小的末尾元素值。这个定义里蕴含一个直觉——同样长度下末尾值越小后面就越有机会接上更大的元素所以每个长度都留一个最优的种子就够用了。关键在于d数组不记录真正的子序列本身只记录如果要凑这个长度末尾可以压到多小。每扫到一个新元素x在d里二分查找第一个大于等于x的位置pos对应严格递增场景用lower_bound对应不降场景用upper_bound。如果pos超出了d的末尾说明x可以接在现有最长的子序列后面直接扩展一位否则用x替换d[pos]让长度为pos1的子序列末尾元素变得更小。int lisOnlogn(vectorint a) { vectorint d; for (int x : a) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) { d.push_back(x); } else { *it x; } } return d.size(); }我拿[3, 1, 4, 1, 5, 9, 2, 6]手推一遍你就能直观看到d的变化过程当前元素d数组变化说明3[3]空数组直接加入1[1]1替换3长度不变末尾更小4[1, 4]4大于末尾扩展长度到21[1, 4]lower_bound找到位置01替换1无变化5[1, 4, 5]扩展长度到39[1, 4, 5, 9]扩展长度到42[1, 2, 5, 9]2替换4长度为2的种子变小6[1, 2, 5, 6]6替换9长度为4的种子变小最终d.size() 4正确答案。观察末尾两行你会发现d数组最后的[1, 2, 5, 6]并不是真实的子序列——真实的[1, 4, 5, 9]和[1, 2, 5, 6]长度一样都是4。这就是d数组的局限性它高效地算长度但如果你直接拿d当结果输出是错的。这个坑我见太多人踩过了。2.3 输出具体子序列记录位置再回溯如果题目不仅要长度还要求输出任意一个最长的递增子序列O(n log n)就不能只维护d了。常见做法是额外开一个pos数组记录每个元素在d中被放到的下标即它作为某个长度的末尾时的长度值再开一个pre数组记录它在原序列中接在哪个元素后面。扫描时如果发现x能扩展pre[当前下标] 实际接上的最后一个元素的下标往后从后往前收集最后反转。说起来有点绕直接看代码更清楚vectorint getLis(vectorint a) { int n a.size(); vectorint d, pos(n), pre(n, -1); for (int i 0; i n; i) { auto it lower_bound(d.begin(), d.end(), a[i]); int p it - d.begin(); if (it d.end()) { d.push_back(a[i]); } else { *it a[i]; } pos[i] p; if (p 0) { // 需要找上一个被放进pos p-1位置的元素下标 } } // ... }实际上要精准维护pre需要记录每个长度对应的实际元素下标也就是d下标对应的原数组下标。完整的写法是维护一个idx数组和pre数组idx[len]表示d中第len个位置上的值来自原数组的哪个下标当x替换d[p]时pre[i] (p 0 ? idx[p-1] : -1)然后idx[p] i。最后从d.size()-1对应的idx开始沿pre一直往前串。核心思想不变d提供贪心择优辅助数组提供重建路径。2.4 变体辨析不降子序列、双端单调序列实际题目很少问裸的LIS常见变体有几个。第一个是最长不降子序列允许相等的元素连续选这时候二分要用upper_bound而不是lower_bound因为等于当前值的元素可以合法地排在后面我们需要找到第一个大于x的位置来替换。第二个是最长递减子序列把数组先整体取负或者把比较符号翻转等价于求原数组的递增子序列。第三个是先增后减的最长双调序列最长先上升再下降子序列做法是从左到右求一遍LIS、从右到左再求一遍LIS然后枚举峰顶答案是left[i] right[i] - 1。这些变体看起来各有花样但内核全是同一个算法面试中被问到变体的本质考察就是你能不能快速识别并复用LIS的解法。3. LCS最长公共子序列二维DP的经典范式3.1 状态定义与转移方程为什么dp[i][j]要这样设计LCS要求在两个字符串a和b中各选一个子序列保持相对顺序且对应位置相等求最大长度。定义dp[i][j]表示a的前i个字符和b的前j个字符的最长公共子序列长度。注意这里的前i个用的是长度语义i和j从0开始dp[0][j]和dp[i][0]全部是0表示有一方是空串时公共子序列长度为0。转移分两种情况。当a[i-1] b[j-1]时说明当前这两个字符可以配对最直观的想法是dp[i][j] dp[i-1][j-1] 1也就是把这两个字符接在各自前缀的最优公共子序列后面。为什么要从dp[i-1][j-1]转移而不是从dp[i-1][j]或dp[i][j-1]转移因为如果从后者转移你无法保证接上的这个字符不跟已经选过的字符冲突。当a[i-1] ! b[j-1]时至少有一个字符不能参与配对所以dp[i][j] max(dp[i-1][j], dp[i][j-1])。代码模板int lcs(string a, string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i-1] b[j-1]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } return dp[n][m]; }这里有个值得多想想的细节为什么两个字符相等时不取max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 1)里面的最大值因为dp[i-1][j-1] 1在这个等条件下一定是三者中最大的dp[i-1][j]最多只比dp[i-1][j-1]多1dp[i][j-1]同理所以直接赋值不会错少写一个max还能省点时间。多问问自己这种小问题比照着代码抄十遍更有效。3.2 表格推演打一遍dp表就知道自己是真懂还是假懂我自己的经验是学二维DP一定要亲手在纸上把dp表填一遍。拿a abcbdabb bdcaba举例先不要看代码按照转移规则一行一行填。填到(i5, j4)那几格时你会切实感受到不相等时取上方和左方较大值是怎么决定状态的。表格填完你会发现dp值是逐行逐列非严格递增的因为公共子序列长度不会因为多看了几个字符反而变短。手动填表还有一个好处能帮你发现下标转换的bug。很多人写代码时在a[i-1]与a[i]之间来回恍惚明明a和b字符串长度一个n一个m却在循环里互相串用下标。手推一遍之后i和j分别对应哪个字符串的哪个位置会非常清晰。3.3 空间优化理解滚动数组的来龙去脉LCS的二维表空间是O(n*m)当两个字符串长度都到5000时表就接近2500万个int内存可能报警。标准优化方法是只保留两行dp[j]表示当前行的值pre[j]表示上一行的值。因为dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]这三格也就是上一行的一格和当前行的左边一格所以逐行滚动更新就够用了。int lcs_optimized(string a, string b) { int m b.size(); vectorint dp(m 1, 0), pre(m 1, 0); for (char ca : a) { for (int j 1; j m; j) { if (ca b[j-1]) dp[j] pre[j-1] 1; else dp[j] max(dp[j-1], pre[j]); } pre dp; } return dp[m]; }这里面最容易犯的错误是在没有保存pre的情况下直接更新dp[j]导致上一行左上方的信息被当前行的更新覆盖。我在初学的时候就不止一次把dp[j-1]和pre[j-1]混用结果答案错得莫名其妙。有的人还会写dp[j] max(dp[j-1], dp[j])这种看似精简的版本其实在取max(d)的时候已经把上一行同列和当前行左边混为一谈因为dp[j]原本是上一行的值dp[j-1]是当前行已更新过的值所以max(dp[j-1], dp[j])恰好等同于max(dp[i][j-1], dp[i-1][j])这个写法是可行的但如果你不理解为什么可行就很难在遇到变体时改对。建议先写两行的版本理解透了再压缩成一行。3.4 回溯重建LCS与边界陷阱输出具体的公共子序列要用完整二维表回溯。从dp[n][m]出发当a[i-1] b[j-1]时说明这个字符被选进公共子序列了记录它然后i--、j--。否则往dp[i-1][j]和dp[i][j-1]里较大的那格走。有个细节两个方向值相等的时候往哪个方向走都行选出来的子序列可能不同但长度一定相同。因此不要指望回溯结果唯一面试里说清楚任意一个最优解即可。边界情况也要养成检查习惯a或b为空串时dp表就是全0参考答案应该是0两个串完全相同时答案是min(n, m)两个串都只有一个字符且不相等时答案是0。这些简单case应该在你写代码之前就在脑子里过一遍而不是写完代码再去测可以省掉大量调试时间。还有一类常见陷阱是字符集很大但没有特殊约束时LCS只能老老实实跑O(n*m)如果有人告诉你用map加线段树能优化到O(n log n)大部分情况是在强行套场景面试时不要主动往那个方向引除非题目明确存在重复字符极少的额外性质。4. LCIS最长公共递增子序列两个模型交叉的进阶题4.1 从LCS到LCIS状态定义为什么需要结尾铺垫现在把LIS和LCS叠加起来在两个数组a和b中找一个最长的公共子序列同时这个子序列的值严格递增。看起来像是LCS的约束多了一个递增很多人的第一反应是加一维状态dp[i][j]表示a的前i个和b的前j个的最长公共递增子序列长度。但这个定义有个致命缺陷——你无法判断新加入的字符是否大于上一个被选中的字符因为状态里没有记录当前公共递增子序列的末尾值是多少。这就是DP状态设计里信息完整度的问题状态必须保留所有影响未来决策的信息。正确的做法是让状态自带结尾锚点定义dp[i][j]为a的前i个元素和b的前j个元素中以b[j]作为最后一个元素的最长公共递增子序列长度。因为我们总是在两个序列里找公共元素末尾元素必然同时出现在a和b中用b[j]做锚点既保留了递增判断所需的末尾值又天然保证了这个子序列在b里的位置就是j。这个定义看起来只是比LCS多了一个条件但是整个转移逻辑就会随之重构。4.2 O(n^3)朴素转移到O(n^2)优化best变量的由来先看朴素转移。当a[i - 1] ! b[j - 1]时a[i]不能和b[j]配对状态无法扩大dp[i][j] dp[i-1][j]相当于只推进a的前缀。当a[i - 1] b[j - 1]时说明找到了一个新的公共对需要枚举在b中j之前所有位置k满足b[k] b[j]把dp[i-1][k]的最大值加1作为新的dp[i][j]。写成公式是dp[i][j] max(dp[i-1][k]) 1其中k j且b[k] b[j]。这个枚举k的过程让整体复杂度达到O(n^3)。关键的优化在于对于固定的i我们按j从小到大的顺序遍历同时维护一个best变量表示当前a[i]之前所有能接上的b[k]中dp[i-1][k]的最大值。具体逻辑在遍历到j时如果b[j] a[i - 1]说明b[j]这个值比当前正在配对的a[i - 1]小未来如果发现在a[i-1]处有相等的j就可以把dp[i-1][j]作为候选接入所以此时更新best max(best, dp[i-1][j])。当a[i - 1] b[j - 1]时直接用best 1去更新dp[i][j]即可。这样每个i扫一遍j时间复杂度降到O(n^2)空间还能用滚动数组压缩。这里有个顺序细节必须在代码里理清best的更新条件用的是b[j] a[i-1]但这个判断和相等匹配的判断在同一个循环里顺序是先处理更新再处理匹配还是反过来我的建议是先判断匹配相等时用best再判断能否更新best因为即使当前b[j]恰好在后面有相等的配对这个b[j]本身不能接在以b[j]结尾的子序列后要求严格递增它的值只能作为未来更大值的候选。代码写法也更清晰int lcis(vectorint a, vectorint b) { int n a.size(), m b.size(); vectorint dp(m 1, 0); for (int i 1; i n; i) { int best 0; for (int j 1; j m; j) { if (a[i-1] b[j-1]) { dp[j] max(dp[j], best 1); } if (b[j-1] a[i-1]) { best max(best, dp[j]); } } } return *max_element(dp.begin(), dp.end()); }注意dp[j]在相等分支更新之后紧接着的if里如果b[j] a[i-1]也成立就用更新后的dp[j]去更新best这样行不行严格递增条件下b[j] a[i-1]且b[j] a[i-1]不可能同时成立所以不会出现刚配对就把自己当作后续候选的问题。不同题解里两个if的顺序略有差异但核心都是在使用和更新之间把握好边界。4.3 手推实例一维dp数组在迭代中的变化拿a {1, 3, 2, 4}b {1, 2, 3, 4}来验证。正确答案是公共递增子序列可以取{1, 2, 4}或{1, 3, 4}长度3。初始dp全0。i1a[0]1时j1b[0]1等于a[0]dp[1] max(0, 01) 1接着判断b[0] 1不成立best保持0。j2b[1]2不等于1判断2 1不成立best仍为0。j3b[2]3不等于1best保持0。j4b[3]4不等于1best为0。第一轮结束dp {1, 0, 0, 0}。i2a[1]3时j1b[0]1不等于3但1 3best max(0, dp[1] 1) 1。j2b[1]2不等于32 3best max(1, dp[2] 0) 1。j3b[2]3等于3dp[3] max(0, best1) 2表示公共递增子序列{1, 3}长度为2随后b[2] 3不成立。j4b[3]4不等于34 3不成立。dp变为{1, 0, 2, 0}。i3a[2]2时j1b[0]1不等于21 2best max(0, 1) 1。j2b[1]2等于2dp[2] max(0, 11) 2表示{1, 2}长度2随后2 2不成立。j3b[2]3不等于23 2不成立。j4同理不成立。dp变为{1, 2, 2, 0}。你看dp[2]变成2是因为best里积累的是以某个小于2的b[k]结尾的最长公共递增子序列长度。i4a[3]4时j11 4best1。j22 4best max(1, dp[2]2) 2。j33 4best max(2, dp[3]2) 2。j4b[3]4等于4dp[4] max(0, 21) 3得到{1, 2, 4}或{1, 3, 4}的长度3。最终max(dp) 3正确。这个手推过程里best一步步累积当前i下所有比a[i]小的候选值的最优长度是理解LCIS优化最直观的方式。4.4 三个模型的关系总结对比看会发现很清晰LIS是单序列、要求递增、答案是max(dp[i])LCS是双序列、要求相等、答案是dp[n][m]LCIS是双序列、要求相等且递增、答案又是max(dp[j])。LIS的答案要取最大值是因为子序列不一定以最后一个元素结尾LCS的答案在dp[n][m]是因为dp[n][m]本来就涵盖了尾部所有情况LCIS的答案在max(dp[j])因为以任意b[j]结尾的最长公共递增子序列都可能成为全局最优。理解答案落在哪个位置背后的原因比背结论重要得多面试追问环节通常就是从这里往下挖的。5. 高频面试变形与实操避坑心得5.1 经典变形题的识别套路面试里最常出现的几个序列题本质上都是这三个模型的马甲。第一个是俄罗斯套娃信封问题每个信封有宽和高一个信封能装进另一个当且仅当宽和高都严格更大求最多能套几层。解法是把信封按宽度升序排序宽度相同时按高度降序排序然后对高度数组跑LIS。宽度升序保证宽度条件是自然满足的宽度相同按高度降序是为了防止相同宽度的信封互相嵌套这个排序trick是题目真正的考点。第二个是最长摆动子序列相邻元素差值正负交替做法是维护up和down两个状态转移时只需比较当前元素和前一个元素的关系比套LCIS还简单但初次见容易慌。第三个是通过删除字符使两个字符串相等最少删除数等于n m - 2 * LCS长度本质上是LCS的逆向应用。第四个是编辑距离只允许插入和删除同样可以转成LCS。拿到这些题先试着把它拆成单序列还是双序列有没有相等约束有没有递增约束框架就出来了。5.2 我在踩坑中总结的几个硬教训第一个坑是LIS的O(n log n)解法里有人误以为返回的是d数组本身的内容题目让输出子序列时直接用d导致结果完全错误。这个问题我在前面已经强调过但还是要重复一遍因为它在讨论区出现的频率太高了。第二个坑是LCIS的dp[j]在滚动数组里可能会残留上一轮的值导致不配对时dp[j]看起来没问题、配对时又莫名多算。最稳的做法是每一轮i循环开始时不要重置整个dp数组而是理解清楚dp[j]在什么时候应该被覆盖成dp[i-1][j]也就是原始二维定义里从上方继承的值。滚动数组版本里不显式做这个继承是因为dp[j]天然保存了上一轮的值这就是滚动的本质。理解不了这一层的建议先写完整二维数组逐行打印出来对照滚动数组版本看差异。第三个坑是下标语义混乱。LCS里dp数组下标代表的是长度不是下标所以访问a[i-1]而不是a[i]LCIS里同样如此。不少人写代码时图省事把dp[i][j]定义成以下标i和j为结尾虽然也能推出正确的转移但初始化时要处理dp[0][]和dp[][0]的边界出错概率更高。我的建议是统一用长度语义虽然代码里多几个减一但更好写、更好检查。5.3 进阶方向刷完这三件套之后往哪走如果这三个模型已经完全吃透下一步值得看几个延伸方向。一个是带路径输出的LIS变体进阶版本要求输出字典序最小的最长递增子序列这需要在二分位置相同时做特殊处理通常从后往前倒推可以当进阶练习题。另一个是树状数组优化LIS当元素值域很大且需要边插入边查询前缀最大值时用离散化加树状数组维护复杂度同样是O(n log n)这种写法在带权的偏序问题里更通用。第三个是LCS的位运算优化bitset做法当字符集很小且字符串很长时可以把LCS加速到O(n*m/字长)虽然面试大概率不考但作为知识拓展很有意思。第四个是最长递增公共子串与LCIS的区别前者要求连续后者允许跳跃转移方程差异恰好是不等时清零还是不等时继承对比着学能帮你把DP的边界条件理解得更细。从LIS到LCS再到LCIS这条路走下来之后你再看大多数序列类型的算法题都会有一种啊这不就是换个约束条件的感觉。我个人的习惯是每学一个模型就顺手把它的状态定义、转移方程、答案位置、时间空间复杂度整理成一张表下次遇到新题先对号入座。最后再分享一个练习小技巧写代码前先在纸上手推一遍小样例写代码后再用同一个样例走查一遍dp表的更新这个方法看起来笨但对建立状态定义到代码下标之间的映射特别有效。真到了面试现场能随手画出dp表、说清楚每个转移理由的人和只会背模板的人表现出来的差距是显而易见的。