1. 项目概述从“最长上升子序列”到动态规划思维模型在算法和数据结构的领域里有些概念就像工具箱里的万能扳手看似解决一个特定问题实则提供了一套可以广泛迁移的思维框架。“最长上升子序列”就是这样一个经典模型。我第一次深入接触它是在准备一场关键的算法面试时面对一道看似复杂的字符串处理问题苦思冥想不得其解。直到我将问题抽象成寻找一个“最优增长序列”瞬间豁然开朗——这不就是LIS的变体吗自那以后无论是在分析用户行为序列、优化任务调度还是在设计缓存淘汰策略时LIS模型及其背后的动态规划思想都成了我高频使用的思维工具。简单来说最长上升子序列问题描述的是给定一个整数序列我们需要找到其中最长的、元素严格递增的子序列的长度。这里的“子序列”意味着可以不连续但必须保持原序列中的相对顺序。例如序列[10, 9, 2, 5, 3, 7, 101, 18]的最长上升子序列之一是[2, 5, 7, 101]长度为4。这个问题之所以重要远不止于它能求出那个长度数字。它本质上是一个关于“序”和“最优子结构”的完美范例其解法——特别是动态规划解法——揭示了如何将全局最优问题分解为层层递进的局部最优子问题这种思想能辐射到无数实际场景中。这篇文章我想和你分享的不仅仅是LIS问题的几种解法代码。我更想拆解这个模型背后的思维逻辑探讨它如何从一个具体的算法题演变成一个可以解决序列优化、路径规划、甚至决策问题的强大模型。无论你是正在刷题求职的开发者还是需要处理序列数据的分析师或是单纯对优化思维感兴趣理解这个模型都能让你多一个清晰有力的分析视角。我们会从最直观的暴力递归开始经历动态规划的优化再到堪称神奇的贪心二分查找解法最后深入它在实际工程中的应用变体。你会发现掌握一个模型比死记硬背十道题的答案要有用得多。2. 核心思路拆解为什么动态规划是“自然”的解法面对“最长”这类优化问题我们的大脑很容易陷入一种暴力枚举的惯性思维找出所有可能的子序列然后判断它们是否上升最后比较长度。这显然是指数级复杂度毫无实用性。那么思维的突破口在哪里关键在于识别问题的两个核心性质最优子结构和重叠子问题。这正是动态规划能够大显身手的前提。2.1 最优子结构从后往前的思维链让我们摒弃“找全局最长”的宏大视角转而思考一个更小的问题“以序列中第i个元素结尾的最长上升子序列长度是多少”我们把这个长度记为dp[i]。为什么这么定义因为一个上升子序列总是以一个具体的元素结尾。如果我们知道了所有以每个位置结尾的最长长度那么整个序列的答案就是这些dp[i]中的最大值。现在关键的一步来了dp[i]怎么求考虑以nums[i]结尾的上升子序列。它的前一个元素nums[j]必然来自i之前的位置j i并且必须满足nums[j] nums[i]。那么以nums[i]结尾的最长序列就是在所有满足条件的j中选择那个能形成最长链的也就是dp[j]最大的那个然后接上nums[i]。于是我们得到了状态转移方程dp[i] max(dp[j]) 1, 对于所有 j i 且 nums[j] nums[i]这个方程就是整个问题的灵魂。它告诉我们大问题以i结尾的最长序列的解可以由小问题以j结尾的最长序列的解推导出来。这就是“最优子结构”一个问题的最优解包含其子问题的最优解。注意这里容易混淆“子序列”和“子问题”。dp[i]定义的是“以i结尾”这个特定子问题的解而不是“从开头到i的序列”这个子问题的解。后者是不正确的因为最长上升子序列不一定以i结尾。这个定义上的细微差别是理解整个解法的关键。2.2 重叠子问题与记忆化避免重复计算的利器如果我们用递归函数根据上面的方程来计算dp[i]会怎样为了计算dp[i]我们需要递归计算所有j i的dp[j]。而计算某个dp[k]时可能又会被多个更大的i所依赖。这样大量的中间结果会被重复计算无数次。例如计算dp[4]时需要dp[0],dp[1],dp[2],dp[3]。计算dp[5]时又需要dp[0]到dp[4]其中dp[0]到dp[3]又被重复计算了。这种性质就是“重叠子问题”。动态规划的第二个核心操作就是解决这个问题记忆化Memoization或制表Tabulation。我们不再用递归树去暴力展开而是用一个数组DP表按顺序存储所有dp[i]的值。计算dp[i]时我们只需要查找表中已经计算好的dp[0]到dp[i-1]的值即可。这实际上是一种“以空间换时间”的策略将指数级复杂度降到了多项式级这里是O(n²)。2.3 从递归到递推两种实现路径理解思路后实现通常有两种方式记忆化搜索自顶向下写一个递归函数dfs(i)返回dp[i]的值。在函数内部如果dp[i]已计算则直接返回否则递归计算所有可能的dp[j]并取最大值1结果存入dp[i]再返回。这种方式更贴近我们最初的思维过程。递推自底向上显式地使用循环。初始化一个长度与序列相同的dp数组每个元素至少为1因为单个元素本身就是一个长度为1的上升子序列。然后用两层循环外层i从0到n-1内层j从0到i-1如果nums[j] nums[i]则尝试更新dp[i] max(dp[i], dp[j] 1)。最后dp数组中的最大值就是答案。在工程和面试中递推写法更为常见因为它避免了递归的函数调用开销且代码结构清晰。其时间复杂度为 O(n²)空间复杂度为 O(n)。def lengthOfLIS_dp(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个位置至少可以构成长度为1的子序列自身 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) # 最终答案是dp数组中的最大值而非dp[-1]实操心得很多初学者会误以为答案是dp[-1]这是错误的。dp[i]只记录了“以i结尾”的最长长度而全局最长子序列不一定以最后一个元素结尾。所以必须遍历整个dp数组取最大值。这是一个经典的陷阱。3. 算法优化贪心二分查找将复杂度降至 O(n log n)O(n²) 的解法对于长度上千的序列可能就有些吃力了。有没有更优的解法有的而且其思路非常巧妙堪称算法设计的典范。这种解法的时间复杂度是 O(n log n)核心在于维护一个“潜在的最优上升子序列”。3.1 核心洞察让序列“长得更慢”我们换一个角度思考。假设我们正在从左到右扫描序列并试图构造一个上升子序列。我们不仅关心当前序列的长度更关心它的“潜力”——为了让后续数字更容易接上我们希望序列末尾的数字尽可能小。基于这个想法我们维护一个数组tails。tails[i]的定义是所有长度为i1的上升子序列中末尾元素的最小值。为什么这个定义有用因为对于固定的长度末尾元素越小未来扩展的可能性就越大。这个数组tails有一个非常重要的性质它是严格递增的。证明如下假设tails[i]是某个长度为i1的子序列的末尾tails[i-1]是某个长度为i的子序列的末尾。由于前者是由后者接上一个更大的数而来所以tails[i] tails[i-1]。3.2 算法流程与二分查找的应用扫描原序列nums中的每个数字x如果x大于tails中所有元素即大于最后一个元素说明我们可以扩展最长序列将x追加到tails末尾。否则我们需要在tails中找到第一个大于或等于x的元素并用x替换它。因为tails是递增的我们可以用二分查找在 O(log n) 时间内完成这个定位。这个“替换”操作是算法的精髓。它并没有改变当前tails数组所代表的序列的实际长度但它让这个“长度为某值的序列的末尾最小值”变得更小从而为未来接纳更多数字创造了条件。def lengthOfLIS_greedy_bisect(nums): tails [] for num in nums: # 使用二分查找在 tails 中寻找第一个 num 的位置 left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid # 如果 left 等于 tails 的长度说明 num 比所有末尾都大 if left len(tails): tails.append(num) else: tails[left] num # 替换使得该长度的末尾元素最小化 return len(tails) # tails 的长度就是最长上升子序列的长度3.3 正确性理解与一个生动的类比这个算法为什么正确我们可以把它想象成“堆箱子”或者“蜘蛛纸牌”的接龙游戏。tails数组的每个位置代表一摞牌或一堆箱子第i摞牌的最上面一张牌就是tails[i]并且从上到下数字递增。我们拿到一张新牌num。规则是只能把牌放在比它小的牌上面。所以我们从左到右查看各摞牌顶找到第一摞牌顶数字大于等于num的把这张牌替换掉如果牌顶和num相等替换不影响结果如果牌顶更大替换使得这摞牌顶变小未来更容易放牌。如果所有牌顶都比num小那就新开一摞。最终摞的数量就是最长上升子序列的长度。这个算法只给出了长度tails数组本身并不一定是一个合法的上升子序列因为其中的元素来自原序列的不同位置可能不满足先后顺序。如果需要还原出具体的序列通常需要配合额外的索引数组来记录路径。注意事项贪心二分法虽然高效但其思维难度远高于动态规划。在面试或竞赛中如果时间紧迫或对正确性没有绝对把握先给出 O(n²) 的动态规划解法并分析复杂度通常是一个更稳妥的策略。可以向面试官说明存在更优的 O(n log n) 解法并简述其思路这既能展示知识广度又避免了在紧张状态下实现复杂算法的风险。4. 模型应用与变体不止于求长度LIS模型之所以强大在于其“寻找最优有序子结构”的核心思想可以应用到各种变体问题上。理解这些变体能极大拓展你解决实际问题的能力。4.1 变体一输出具体的序列内容很多时候我们不仅需要长度还需要知道这个子序列具体是什么。对于动态规划解法我们在状态转移时额外维护一个prev[i]数组记录在形成dp[i]时其前驱元素的下标j。计算结束后我们先找到dp数组中最大值对应的下标max_index然后通过prev数组向前回溯即可得到逆序的序列最后反转即可。def lengthOfLIS_with_path(nums): if not nums: return 0, [] n len(nums) dp [1] * n prev [-1] * n # 记录前驱索引-1表示无前驱序列开头 for i in range(n): for j in range(i): if nums[j] nums[i] and dp[j] 1 dp[i]: dp[i] dp[j] 1 prev[i] j # 记录是从j转移过来的 max_len 0 max_index -1 for i in range(n): if dp[i] max_len: max_len dp[i] max_index i # 回溯构造序列 path [] while max_index ! -1: path.append(nums[max_index]) max_index prev[max_index] path.reverse() return max_len, path4.2 变体二非严格递增/递减/不上升子序列模型可以轻松调整比较条件来处理不同情况最长不下降子序列非严格递增将状态转移条件nums[j] nums[i]改为nums[j] nums[i]。最长下降子序列可以将序列反转后求LIS或者将比较条件改为nums[j] nums[i]。最长不上升子序列非严格递减类似地调整条件即可。4.3 变体三二维及多维LIS问题俄罗斯套娃信封问题这是一个经典的LIS变体问题给定一些信封的宽度和高度(w, h)如果一个信封的宽度和高度都大于另一个信封那么它可以套住另一个信封。问最多能套多少层。解决思路是降维首先对信封排序按宽度w升序排序当宽度相同时按高度h降序排序。为什么高度要降序这是为了避免宽度相同的信封被错误地认为可以嵌套宽度相同不符合“都大于”的条件。降序保证了在查找LIS时宽度相同的信封不会相互构成递增关系。排序后问题就转化为在高度数组h上寻找最长严格上升子序列。因为宽度已经有序非递减我们只需要保证高度是严格递增的就能满足“宽度和高度都递增”的条件。def maxEnvelopes(envelopes): if not envelopes: return 0 # 排序宽度升序宽度相同时高度降序 envelopes.sort(keylambda x: (x[0], -x[1])) # 提取高度序列 heights [h for _, h in envelopes] # 在高度序列上求LIS使用O(n log n)的贪心二分法 tails [] for h in heights: left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] h: left mid 1 else: right mid if left len(tails): tails.append(h) else: tails[left] h return len(tails)这个变体完美展示了如何通过巧妙的预处理排序将复杂的二维约束问题转化为我们熟悉的一维LIS模型。4.4 实际工程场景联想LIS的思想在工程中也有很多映射版本兼容性/依赖链分析一系列软件版本新版本需要兼容旧版本。寻找最长的兼容版本链可以抽象为LIS问题“兼容”相当于“小于”或“小于等于”。任务调度与资源分配有一系列任务每个任务有开始时间和结束时间且需要同一资源。如果我们将任务按某种规则排序如开始时间那么能连续执行的任务序列可能对应一个“上升”序列。用户行为序列分析分析用户操作日志寻找最长的、符合某种业务逻辑的连续操作模式例如页面浏览深度逐渐加深的序列。5. 常见问题与排查技巧实录在实际编码和面试中围绕LIS模型会遇到一些典型问题。这里我总结了一份“避坑指南”。5.1 问题一初始化与边界条件处理问题表现程序在空数组输入时崩溃或者结果总是少1。根因分析空输入未检查输入数组nums是否为空。直接访问nums[0]或计算len(nums)会导致错误。dp数组初始化在动态规划解法中dp数组的每个位置至少为1因为单个元素本身就是一个子序列。如果错误地初始化为0结果会出错。返回值动态规划解法最后需要返回max(dp)而不是dp[-1]。解决方案def lengthOfLIS_safe(nums): if not nums: # 处理空输入 return 0 n len(nums) dp [1] * n # 正确初始化每个位置至少长度为1 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) # 返回dp数组中的最大值注意不是dp[-1]5.2 问题二贪心二分法中二分查找的细节问题表现使用贪心二分法时得到的长度偶尔不正确特别是在有重复数字的序列中。根因分析二分查找的目标是找到tails数组中第一个大于或等于x的位置对于严格上升子序列。如果查找的是“第一个大于x的位置”当tails中存在等于x的元素时就会错过替换机会可能导致结果偏大因为允许了相等元素变成了非严格递增。反之如果目标是“第一个大于x的位置”对于严格递增LIS是正确的但代码实现时左右边界收缩容易出错。解决方案严格统一二分查找的语义。对于严格上升子序列(LIS)我们寻找tails中第一个 num的位置进行替换。这保证了tails数组的严格递增性。可以使用bisect_left函数如果语言支持来避免手写二分的错误。import bisect def lengthOfLIS_bisect(nums): tails [] for num in nums: pos bisect.bisect_left(tails, num) # 找到第一个 num 的位置 if pos len(tails): tails.append(num) else: tails[pos] num return len(tails)实操心得手写二分查找是面试常考点务必熟练掌握两种模板寻找左边界bisect_left和寻找右边界bisect_right。在LIS问题中使用bisect_left。一个简单的记忆方法是我们要维持tails的递增性新来的num应该替换掉第一个不小于它的数以保持序列“尽可能小”这正是bisect_left的功能。5.3 问题三变体问题中的排序陷阱问题表现在解决“俄罗斯套娃信封”这类二维问题时排序策略错误导致结果不正确。根因分析排序时只考虑了宽度升序当宽度相同时如果高度也按升序排序那么[(1,2), (1,3), (1,4)]在高度序列[2,3,4]上求LIS会得到3。但实际上宽度相同的信封不能相互嵌套正确答案应该是1。错误的排序让宽度相同的信封在高度上形成了递增关系被算法误认为可以嵌套。解决方案牢记排序规则——第一维升序第一维相同时第二维降序。降序的目的就是为了破坏宽度相同时高度上的递增关系确保在后续的LIS计算中它们不会构成合法序列。# 正确的排序关键函数 envelopes.sort(keylambda x: (x[0], -x[1]))5.4 性能考量与算法选择场景对比数据规模小 (n 1000)O(n²)的动态规划解法完全够用代码简单不易出错且便于输出具体序列。数据规模大 (n 1000)必须使用O(n log n)的贪心二分法。尤其是在在线判题系统或处理真实业务数据时。需要输出具体序列优先选择动态规划路径回溯。贪心二分法虽然高效但tails数组并非真实序列还原路径需要更复杂的记录通常不直观。问题变体复杂如涉及二维属性先思考能否通过排序等预处理转化为标准LIS。动态规划的框架更容易嵌入额外的状态维度。在我个人的经验中LIS模型是检验对动态规划理解深度的试金石。它从最朴素的重复子问题开始引出状态定义的艺术再通过贪心策略进行优化最后其思想能迁移到各种高维场景。掌握它不仅仅是学会了一道题更是掌握了一种“化序为链求最优子结构”的通用思维模式。下次当你遇到任何涉及序列、选择、最优的问题时不妨先问问自己这里面的“上升子序列”在哪里
