1. 从“最长上升子序列”到“子问题”的本质一个动态规划的思维起点动态规划Dynamic Programming, DP这个名字听起来挺唬人好像是什么高深莫测的“规划”。但在我自己学习和后来带新人的过程中我发现很多人卡住不是因为算法本身多难而是从一开始就没搞明白“子问题”到底是什么以及我们为什么要费劲去分析它。今天我们就拿一个经典得不能再经典的题目——最长上升子序列Longest Increasing Subsequence, LIS——作为手术刀来解剖一下“子问题分析”这个动态规划最核心的思维过程。这不是一篇罗列公式的教程而是想跟你聊聊当我在白板上画下第一个状态定义时脑子里到底在转些什么。为什么是LIS因为它足够简单也足够典型。简单在于它的题意一目了然给你一个整数序列找出其中最长的一个子序列使得这个子序列里的元素是严格递增的。典型在于它完美地展示了动态规划中“无后效性”和“最优子结构”这两个抽象概念的具体模样。我们不需要任何高深的数学只需要跟着问题本身一步步推导。你会发现所谓的“状态定义”和“状态转移方程”不是凭空变出来的魔术而是你对问题理解深度的一种自然表达。如果你曾经对着一道DP题感觉答案呼之欲出却又不知从何下手那么希望这次“子问题分析”的慢镜头回放能给你带来一些不一样的启发。2. 暴力穷举的困境为什么我们“想”不出答案面对“最长上升子序列”这个问题最直接也是最笨的想法是什么没错暴力枚举。给定一个长度为n的序列它的所有子序列有多少个是2^n个。因为每个元素都有“选”或“不选”两种可能。对于每一个子序列我们还需要检查它是否是递增的这又需要O(k)的时间k是子序列长度。所以总的时间复杂度是O(n * 2^n)。当n30时这个数字已经大到无法接受。但这里有一个更关键的问题它比“算得慢”更致命暴力枚举无法给我们提供“构造”最优解的清晰思路。它只是机械地列举所有可能性然后比较。这就像你想知道从家到公司最快的一条路你的方法是把世界上所有可能的路径都走一遍并计时。你最终确实能得到答案但你在这个过程中没有积累任何关于“为什么这条路快”的知识。你不知道哪个路口的选择是关键也不知道一段拥堵是如何影响全局的。所以动态规划的第一步就是拒绝这种“一锤子买卖”式的暴力转而思考我们能不能把“找整个序列的最长上升子序列”这个大问题拆解成一系列更小的、结构相似的、并且更容易解决的“小问题”这些小问题就是“子问题”。一个好的子问题划分应该能让我们通过解决这些小问题并巧妙地组合它们的答案最终得到大问题的答案。这就是“最优子结构”的通俗理解大问题的最优解可以由其小问题的最优解组合而成。3. 子问题定义的探索几种思路的碰撞与选择那么对于LIS我们怎么定义子问题呢这并不是一个显而易见的步骤也是新手最容易卡住的地方。我们不妨来头脑风暴几种常见的思路看看它们的优劣。思路一子问题定义为dp[i]表示“以第i个元素结尾的上升子序列”的集合。这个想法很自然因为它把问题的关注点从“整个序列”缩小到了“序列的前缀部分”。但仔细一想dp[i]如果表示一个“集合”那它就不是一个可以简单传递的“值”。我们需要的是能推导出其他状态的一个“状态值”。所以我们需要从这个集合里提炼出一个最关键的信息。什么信息最关键既然是“最长”那么对于以i结尾的所有上升子序列我们只关心其中最长的那个的长度。于是我们得到了第一个可能的状态定义dp[i]表示以第i个元素nums[i]结尾的最长上升子序列的长度。这个定义好吗我们暂时保留。先看其他思路。思路二子问题定义为dp[i]表示“序列前i个元素中的最长上升子序列”的长度。这个定义似乎更贴近原问题。原问题是“整个序列”这里是“前i个元素”。那么dp[n]就是我们想要的最终答案。这个定义看起来非常直接。但是当我们尝试思考dp[i]和dp[i-1]的关系时会遇到一个麻烦前i个元素的最长上升子序列未必包含第i个元素。也就是说dp[i]有可能等于dp[i-1]。这本身没问题但关键在于当它包含第i个元素时我们怎么利用之前的结果我们不知道前i-1个元素中哪个以某个元素结尾的上升子序列能接上nums[i]。我们发现仅仅知道“前i-1个元素的LIS长度”这个信息太少了不足以判断nums[i]是否能接在某个子序列后面形成更长的。我们缺少了关于“结尾数字”的信息。思路三结合前两者定义dp[i]表示“长度为i1的上升子序列中最小的结尾数字是多少”。这是一个非常巧妙但不太直观的思路它最终会引向O(n log n)的二分查找解法。它完全改变了状态的含义不再直接表示“长度”而是用状态下标表示长度状态值表示该长度下“最好”的结尾数字为了能接上更多的后续数字结尾数字越小潜力越大。这个思路对于初学者理解“子问题”来说跳跃性太大。我们首先要掌握最基础、最符合直觉的模型。回到思路一。为什么它更常被作为DP解法的起点因为它无后效性体现得非常清晰。dp[i]的值只取决于它之前的、那些结尾数字比nums[i]小的状态dp[j](j i)。一旦dp[i]被计算出来它就是一个确定的数字后续状态在计算时只需要看到这个“长度”数字和对应的“结尾值”nums[i]而不需要关心这个以i结尾的LIS具体是由哪些前面的元素构成的。这完美符合动态规划的要求。所以我们选择第一个思路作为我们子问题分析的基础定义dp[i]为以nums[i]结尾的最长上升子序列的长度。注意这里蕴含了一个重要的DP思维——当直接定义“前i个元素的解”遇到困难时尝试定义“以第i个元素为结尾的解”。后者往往能携带更具体的信息结尾元素的值从而让状态转移成为可能。4. 状态转移方程的推导如何用“已知”拼凑“未知”定义好了子问题下一步就是建立它们之间的联系也就是状态转移方程。我们要用数学或者说逻辑语言描述出dp[i]怎么由之前的dp[0...i-1]推导出来。根据定义dp[i]是以nums[i]结尾的LIS长度。那么什么样的序列能以nums[i]结尾呢它必然是由一个在i之前的、以某个nums[j]结尾的上升子序列后面加上nums[i]构成的。当然这个nums[j]必须满足nums[j] nums[i]这样才能保证递增。并且我们希望这个接上去之后的序列是最长的。所以我们应该在所有满足j i且nums[j] nums[i]的j中找到那个dp[j]最大的然后在其基础上加1。因为dp[j]本身就代表了以nums[j]结尾的最长长度接上nums[i]后长度自然就是dp[j] 1。如果不存在这样的j即i之前的所有元素都比nums[i]大那么以nums[i]结尾的LIS就只包含它自己长度为1。把上面的逻辑翻译成公式就是dp[i] max(1, max{ dp[j] 1 | for all j i and nums[j] nums[i] })或者更清晰地写成伪代码初始化 dp 数组所有元素为 1 // 每个元素自身至少是一个长度为1的LIS for i from 0 to n-1: for j from 0 to i-1: if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1)最终整个序列的LIS长度就是dp数组中的最大值max(dp[0], dp[1], ..., dp[n-1])。为什么这样是对的——最优子结构的体现这里清晰地展示了最优子结构为了求解以i结尾的最优解dp[i]我们需要遍历所有可能的“前驱状态”j并利用它们的最优解dp[j]来构造自己的解。dp[i]的构建完全依赖于子问题dp[j]的最优解。整个大问题整个序列的LIS的最优解则是所有子问题最优解dp[i]中的最大值。5. 从理论到代码实现细节与时空复杂度分析理论清晰后实现就是水到渠成。我们以经典的[10, 9, 2, 5, 3, 7, 101, 18]为例走一遍流程。5.1 手动模拟过程初始化dp [1, 1, 1, 1, 1, 1, 1, 1]。i0(nums[0]10): 前面没有元素dp[0]保持为1。i1(nums[1]9): 检查 j0nums[0]10 9不满足上升条件。dp[1]保持为1。i2(nums[2]2): 检查 j0,1。nums[0]10 2 nums[1]9 2。dp[2]保持为1。i3(nums[3]5):j0: 10 5跳过。j1: 9 5跳过。j2: 2 5此时dp[2]1所以dp[3] max(dp[3], dp[2]1) max(1, 11) 2。最终dp[3]2对应序列[2, 5]。i4(nums[4]3):j2: 2 3dp[4] max(1, 11) 2(序列[2, 3])。j3: 5 3跳过。最终dp[4]2。i5(nums[5]7):j2: 2 7dp[5] max(1, 11) 2。j3: 5 7dp[5] max(2, 21) 3(序列[2, 5, 7])。j4: 3 7dp[5] max(3, 21) 3(序列[2, 3, 7]长度也是3)。最终dp[5]3。i6(nums[6]101):遍历前面所有 j 能接在很多序列后面最终会找到最长的dp[5]3 所以dp[6] 31 4(序列可以是[2, 5, 7, 101]或[2, 3, 7, 101])。i7(nums[7]18):同样遍历最长可接在dp[5]3后面dp[7] 31 4(序列[2, 5, 7, 18]或[2, 3, 7, 18])。最终dp [1, 1, 1, 2, 2, 3, 4, 4]最大值是4所以LIS长度是4。5.2 代码实现Pythondef length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 初始化每个元素自身就是一个长度为1的LIS max_length 1 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) max_length max(max_length, dp[i]) # 随时更新全局最大值 return max_length # 测试 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis(nums)) # 输出45.3 复杂度分析时间复杂度O(n²)。两层嵌套循环对于每个i最坏情况下要遍历前面所有的j。空间复杂度O(n)。只需要一个长度为n的dp数组。对于n在 10³ 数量级以内的问题这个解法是完全可行的。这也是动态规划最基础的模板之一。6. 陷阱、变种与进阶思考子问题分析的延伸掌握了基础模型我们才能谈得上识别陷阱和应对变种。很多DP难题其实就是子问题定义和状态转移条件变得更加隐蔽或复杂。6.1 一个常见陷阱“非连续”与“子序列”LIS问题要求是“子序列”而不是“子数组”。子序列可以不连续这是DP解法成立的关键。如果题目改成“最长连续递增子序列”那就简单多了用滑动窗口或一次遍历即可完全不需要DP。一定要仔细审题。6.2 变种一输出具体的LIS序列我们的dp数组只存储了长度。如何输出一个具体的序列呢这需要在状态转移时额外记录“前驱节点”。我们引入一个prev数组prev[i]表示在以nums[i]结尾的LIS中nums[i]的前一个元素的下标。def length_of_lis_and_path(nums): if not nums: return 0, [] n len(nums) dp [1] * n prev [-1] * n # -1 表示没有前驱即序列开头 max_len 1 end_idx 0 # 记录最长LIS的最后一个元素下标 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 # 记录前驱 if dp[i] max_len: max_len dp[i] end_idx i # 回溯构造序列 path [] while end_idx ! -1: path.append(nums[end_idx]) end_idx prev[end_idx] path.reverse() # 回溯得到的是逆序需要反转 return max_len, path这个技巧在需要还原DP路径的问题中非常常见例如最短路径、编辑距离等。6.3 变种二O(n log n) 的贪心二分查找解法当n很大例如 10⁵时O(n²) 的算法会超时。这就需要更优的算法。其核心是改变子问题的定义也就是我们之前提到的思路三。 我们维护一个数组tails其中tails[len]表示长度为len1的所有上升子序列中结尾数字最小的那个。 遍历原数组nums如果nums[i]比tails中所有元素都大说明它可以接在最长的子序列后面形成更长的序列于是将其追加到tails末尾。否则在tails中找到第一个大于等于nums[i]的元素用nums[i]替换它。因为对于同样长度的上升子序列结尾数字越小未来“潜力”越大。由于tails数组是单调递增的查找可以用二分查找复杂度 O(log n)。def length_of_lis_nlogn(nums): tails [] for num in nums: # 二分查找 leftmost position to replace left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) # 比所有都大延长序列 else: tails[left] num # 替换优化潜力 return len(tails) # tails的长度就是LIS的长度这个解法的时间复杂度是 O(n log n)空间复杂度 O(n)。它体现了动态规划与贪心、二分查找结合的强大威力。理解这个解法的关键在于tails数组本身并不是一个真实的LIS但它维护了各个长度下最优的“结尾最小值”从而保证了最终长度的正确性。这是一种“状态压缩”和“定义优化”的极致体现。6.4 从LIS到其他经典问题LIS的子问题分析模式可以迁移到许多其他问题上最大子数组和Maximum Subarraydp[i]定义为以nums[i]结尾的最大子数组和。状态转移dp[i] max(nums[i], dp[i-1] nums[i])。同样是“以i结尾”的定义。最长公共子序列LCS子问题定义为dp[i][j]表示字符串A[0..i]和B[0..j]的LCS长度。状态转移需要考虑字符是否相等。编辑距离Edit Distance子问题定义为dp[i][j]表示将单词A[0..i]转换为B[0..j]所需的最少操作数。它们的共性在于都通过一个精巧的状态定义通常是二维如LCS、编辑距离将原问题分解为规模更小的子问题并通过状态转移方程建立起子问题之间的联系。7. 实战心得如何训练“子问题分析”的肌肉记忆最后分享几点我个人在学习和教学DP时的体会这些是书本和标准题解里不会写的“软经验”。7.1 从“记忆”到“推导”不要一上来就背“dp数组定义”和“状态转移方程”。对于每一道新题强迫自己拿出一张白纸从问题描述开始尝试自己定义子问题。问自己我最关心什么信息什么样的子问题规模更小且结构相同这个子问题的解能否帮助我解决更大的问题这个过程一开始会很慢甚至会走错路就像我们对比了LIS的几种定义思路但这是形成DP直觉的唯一途径。走错路然后修正比直接走对路学到的东西更多。7.2 重视“手动模拟”在得出状态转移方程后不要急着写代码。一定要找一个小的、非平凡的实例比如长度5-6的数组手动模拟整个dp数组的填充过程。这个过程能帮你验证方程的正确性逻辑推导可能隐藏着边界错误手动算一遍能立刻发现。理解表的含义看着dp[i]一个个被算出来你会对“状态”和“转移”有更感性的认识。调试的预演如果代码出错你手算的表格就是最可靠的对照标准。7.3 思考“如果我是计算机”这是理解DP“自底向上”填表法的好方法。想象你是一台只能进行简单计算和记忆的机器。你有一个表格dp数组。你被问到dp[5]是多少。你不知道但你知道规则dp[5]取决于dp[0]到dp[4]以及它们对应的数字大小。所以你只好从dp[0]开始根据初始条件比如dp[0]1把它填上。然后根据dp[0]和规则去填dp[1]依此类推。这个过程就是动态规划的计算过程——从小问题开始逐步解决大问题并记住所有子问题的解以避免重复计算。7.4 对比“递归记忆化搜索”动态规划的递推写法自底向上填表和递归加记忆化搜索自顶向下是等价的只是思考方向不同。对于某些问题从原问题出发思考“要解决这个问题需要先解决哪些子问题”这种递归的思路可能更自然。例如在LIS中可以定义函数dfs(i)返回以i结尾的LIS长度其内部会递归调用dfs(j)j i。然后用一个数组memo存储dfs(i)的结果避免重复计算。这两种方法本质是一体两面都体现了“重叠子问题”和“最优子结构”。初学者可以都尝试实现加深理解。动态规划的精髓不在于记住多少个模板而在于掌握这种“定义子问题-建立联系-高效求解”的思维模式。LIS作为一个入门案例几乎包含了DP的所有核心概念。把它吃透再去看背包、区间DP、状态压缩DP你会发现它们都是在这个基本范式上的扩展和变形。子问题分析就是打开动态规划大门的钥匙而练习是让这把钥匙变得好用的唯一方法。 
长河君 · 2026/8/28 4:23:54 · 阅读 1.2k 动态规划入门：从最长上升子序列剖析子问题定义与状态转移
1. 从“最长上升子序列”到“子问题”的本质一个动态规划的思维起点动态规划Dynamic Programming, DP这个名字听起来挺唬人好像是什么高深莫测的“规划”。但在我自己学习和后来带新人的过程中我发现很多人卡住不是因为算法本身多难而是从一开始就没搞明白“子问题”到底是什么以及我们为什么要费劲去分析它。今天我们就拿一个经典得不能再经典的题目——最长上升子序列Longest Increasing Subsequence, LIS——作为手术刀来解剖一下“子问题分析”这个动态规划最核心的思维过程。这不是一篇罗列公式的教程而是想跟你聊聊当我在白板上画下第一个状态定义时脑子里到底在转些什么。为什么是LIS因为它足够简单也足够典型。简单在于它的题意一目了然给你一个整数序列找出其中最长的一个子序列使得这个子序列里的元素是严格递增的。典型在于它完美地展示了动态规划中“无后效性”和“最优子结构”这两个抽象概念的具体模样。我们不需要任何高深的数学只需要跟着问题本身一步步推导。你会发现所谓的“状态定义”和“状态转移方程”不是凭空变出来的魔术而是你对问题理解深度的一种自然表达。如果你曾经对着一道DP题感觉答案呼之欲出却又不知从何下手那么希望这次“子问题分析”的慢镜头回放能给你带来一些不一样的启发。2. 暴力穷举的困境为什么我们“想”不出答案面对“最长上升子序列”这个问题最直接也是最笨的想法是什么没错暴力枚举。给定一个长度为n的序列它的所有子序列有多少个是2^n个。因为每个元素都有“选”或“不选”两种可能。对于每一个子序列我们还需要检查它是否是递增的这又需要O(k)的时间k是子序列长度。所以总的时间复杂度是O(n * 2^n)。当n30时这个数字已经大到无法接受。但这里有一个更关键的问题它比“算得慢”更致命暴力枚举无法给我们提供“构造”最优解的清晰思路。它只是机械地列举所有可能性然后比较。这就像你想知道从家到公司最快的一条路你的方法是把世界上所有可能的路径都走一遍并计时。你最终确实能得到答案但你在这个过程中没有积累任何关于“为什么这条路快”的知识。你不知道哪个路口的选择是关键也不知道一段拥堵是如何影响全局的。所以动态规划的第一步就是拒绝这种“一锤子买卖”式的暴力转而思考我们能不能把“找整个序列的最长上升子序列”这个大问题拆解成一系列更小的、结构相似的、并且更容易解决的“小问题”这些小问题就是“子问题”。一个好的子问题划分应该能让我们通过解决这些小问题并巧妙地组合它们的答案最终得到大问题的答案。这就是“最优子结构”的通俗理解大问题的最优解可以由其小问题的最优解组合而成。3. 子问题定义的探索几种思路的碰撞与选择那么对于LIS我们怎么定义子问题呢这并不是一个显而易见的步骤也是新手最容易卡住的地方。我们不妨来头脑风暴几种常见的思路看看它们的优劣。思路一子问题定义为dp[i]表示“以第i个元素结尾的上升子序列”的集合。这个想法很自然因为它把问题的关注点从“整个序列”缩小到了“序列的前缀部分”。但仔细一想dp[i]如果表示一个“集合”那它就不是一个可以简单传递的“值”。我们需要的是能推导出其他状态的一个“状态值”。所以我们需要从这个集合里提炼出一个最关键的信息。什么信息最关键既然是“最长”那么对于以i结尾的所有上升子序列我们只关心其中最长的那个的长度。于是我们得到了第一个可能的状态定义dp[i]表示以第i个元素nums[i]结尾的最长上升子序列的长度。这个定义好吗我们暂时保留。先看其他思路。思路二子问题定义为dp[i]表示“序列前i个元素中的最长上升子序列”的长度。这个定义似乎更贴近原问题。原问题是“整个序列”这里是“前i个元素”。那么dp[n]就是我们想要的最终答案。这个定义看起来非常直接。但是当我们尝试思考dp[i]和dp[i-1]的关系时会遇到一个麻烦前i个元素的最长上升子序列未必包含第i个元素。也就是说dp[i]有可能等于dp[i-1]。这本身没问题但关键在于当它包含第i个元素时我们怎么利用之前的结果我们不知道前i-1个元素中哪个以某个元素结尾的上升子序列能接上nums[i]。我们发现仅仅知道“前i-1个元素的LIS长度”这个信息太少了不足以判断nums[i]是否能接在某个子序列后面形成更长的。我们缺少了关于“结尾数字”的信息。思路三结合前两者定义dp[i]表示“长度为i1的上升子序列中最小的结尾数字是多少”。这是一个非常巧妙但不太直观的思路它最终会引向O(n log n)的二分查找解法。它完全改变了状态的含义不再直接表示“长度”而是用状态下标表示长度状态值表示该长度下“最好”的结尾数字为了能接上更多的后续数字结尾数字越小潜力越大。这个思路对于初学者理解“子问题”来说跳跃性太大。我们首先要掌握最基础、最符合直觉的模型。回到思路一。为什么它更常被作为DP解法的起点因为它无后效性体现得非常清晰。dp[i]的值只取决于它之前的、那些结尾数字比nums[i]小的状态dp[j](j i)。一旦dp[i]被计算出来它就是一个确定的数字后续状态在计算时只需要看到这个“长度”数字和对应的“结尾值”nums[i]而不需要关心这个以i结尾的LIS具体是由哪些前面的元素构成的。这完美符合动态规划的要求。所以我们选择第一个思路作为我们子问题分析的基础定义dp[i]为以nums[i]结尾的最长上升子序列的长度。注意这里蕴含了一个重要的DP思维——当直接定义“前i个元素的解”遇到困难时尝试定义“以第i个元素为结尾的解”。后者往往能携带更具体的信息结尾元素的值从而让状态转移成为可能。4. 状态转移方程的推导如何用“已知”拼凑“未知”定义好了子问题下一步就是建立它们之间的联系也就是状态转移方程。我们要用数学或者说逻辑语言描述出dp[i]怎么由之前的dp[0...i-1]推导出来。根据定义dp[i]是以nums[i]结尾的LIS长度。那么什么样的序列能以nums[i]结尾呢它必然是由一个在i之前的、以某个nums[j]结尾的上升子序列后面加上nums[i]构成的。当然这个nums[j]必须满足nums[j] nums[i]这样才能保证递增。并且我们希望这个接上去之后的序列是最长的。所以我们应该在所有满足j i且nums[j] nums[i]的j中找到那个dp[j]最大的然后在其基础上加1。因为dp[j]本身就代表了以nums[j]结尾的最长长度接上nums[i]后长度自然就是dp[j] 1。如果不存在这样的j即i之前的所有元素都比nums[i]大那么以nums[i]结尾的LIS就只包含它自己长度为1。把上面的逻辑翻译成公式就是dp[i] max(1, max{ dp[j] 1 | for all j i and nums[j] nums[i] })或者更清晰地写成伪代码初始化 dp 数组所有元素为 1 // 每个元素自身至少是一个长度为1的LIS for i from 0 to n-1: for j from 0 to i-1: if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1)最终整个序列的LIS长度就是dp数组中的最大值max(dp[0], dp[1], ..., dp[n-1])。为什么这样是对的——最优子结构的体现这里清晰地展示了最优子结构为了求解以i结尾的最优解dp[i]我们需要遍历所有可能的“前驱状态”j并利用它们的最优解dp[j]来构造自己的解。dp[i]的构建完全依赖于子问题dp[j]的最优解。整个大问题整个序列的LIS的最优解则是所有子问题最优解dp[i]中的最大值。5. 从理论到代码实现细节与时空复杂度分析理论清晰后实现就是水到渠成。我们以经典的[10, 9, 2, 5, 3, 7, 101, 18]为例走一遍流程。5.1 手动模拟过程初始化dp [1, 1, 1, 1, 1, 1, 1, 1]。i0(nums[0]10): 前面没有元素dp[0]保持为1。i1(nums[1]9): 检查 j0nums[0]10 9不满足上升条件。dp[1]保持为1。i2(nums[2]2): 检查 j0,1。nums[0]10 2 nums[1]9 2。dp[2]保持为1。i3(nums[3]5):j0: 10 5跳过。j1: 9 5跳过。j2: 2 5此时dp[2]1所以dp[3] max(dp[3], dp[2]1) max(1, 11) 2。最终dp[3]2对应序列[2, 5]。i4(nums[4]3):j2: 2 3dp[4] max(1, 11) 2(序列[2, 3])。j3: 5 3跳过。最终dp[4]2。i5(nums[5]7):j2: 2 7dp[5] max(1, 11) 2。j3: 5 7dp[5] max(2, 21) 3(序列[2, 5, 7])。j4: 3 7dp[5] max(3, 21) 3(序列[2, 3, 7]长度也是3)。最终dp[5]3。i6(nums[6]101):遍历前面所有 j 能接在很多序列后面最终会找到最长的dp[5]3 所以dp[6] 31 4(序列可以是[2, 5, 7, 101]或[2, 3, 7, 101])。i7(nums[7]18):同样遍历最长可接在dp[5]3后面dp[7] 31 4(序列[2, 5, 7, 18]或[2, 3, 7, 18])。最终dp [1, 1, 1, 2, 2, 3, 4, 4]最大值是4所以LIS长度是4。5.2 代码实现Pythondef length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 初始化每个元素自身就是一个长度为1的LIS max_length 1 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) max_length max(max_length, dp[i]) # 随时更新全局最大值 return max_length # 测试 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis(nums)) # 输出45.3 复杂度分析时间复杂度O(n²)。两层嵌套循环对于每个i最坏情况下要遍历前面所有的j。空间复杂度O(n)。只需要一个长度为n的dp数组。对于n在 10³ 数量级以内的问题这个解法是完全可行的。这也是动态规划最基础的模板之一。6. 陷阱、变种与进阶思考子问题分析的延伸掌握了基础模型我们才能谈得上识别陷阱和应对变种。很多DP难题其实就是子问题定义和状态转移条件变得更加隐蔽或复杂。6.1 一个常见陷阱“非连续”与“子序列”LIS问题要求是“子序列”而不是“子数组”。子序列可以不连续这是DP解法成立的关键。如果题目改成“最长连续递增子序列”那就简单多了用滑动窗口或一次遍历即可完全不需要DP。一定要仔细审题。6.2 变种一输出具体的LIS序列我们的dp数组只存储了长度。如何输出一个具体的序列呢这需要在状态转移时额外记录“前驱节点”。我们引入一个prev数组prev[i]表示在以nums[i]结尾的LIS中nums[i]的前一个元素的下标。def length_of_lis_and_path(nums): if not nums: return 0, [] n len(nums) dp [1] * n prev [-1] * n # -1 表示没有前驱即序列开头 max_len 1 end_idx 0 # 记录最长LIS的最后一个元素下标 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 # 记录前驱 if dp[i] max_len: max_len dp[i] end_idx i # 回溯构造序列 path [] while end_idx ! -1: path.append(nums[end_idx]) end_idx prev[end_idx] path.reverse() # 回溯得到的是逆序需要反转 return max_len, path这个技巧在需要还原DP路径的问题中非常常见例如最短路径、编辑距离等。6.3 变种二O(n log n) 的贪心二分查找解法当n很大例如 10⁵时O(n²) 的算法会超时。这就需要更优的算法。其核心是改变子问题的定义也就是我们之前提到的思路三。 我们维护一个数组tails其中tails[len]表示长度为len1的所有上升子序列中结尾数字最小的那个。 遍历原数组nums如果nums[i]比tails中所有元素都大说明它可以接在最长的子序列后面形成更长的序列于是将其追加到tails末尾。否则在tails中找到第一个大于等于nums[i]的元素用nums[i]替换它。因为对于同样长度的上升子序列结尾数字越小未来“潜力”越大。由于tails数组是单调递增的查找可以用二分查找复杂度 O(log n)。def length_of_lis_nlogn(nums): tails [] for num in nums: # 二分查找 leftmost position to replace left, right 0, len(tails) while left right: mid (left right) // 2 if tails[mid] num: left mid 1 else: right mid if left len(tails): tails.append(num) # 比所有都大延长序列 else: tails[left] num # 替换优化潜力 return len(tails) # tails的长度就是LIS的长度这个解法的时间复杂度是 O(n log n)空间复杂度 O(n)。它体现了动态规划与贪心、二分查找结合的强大威力。理解这个解法的关键在于tails数组本身并不是一个真实的LIS但它维护了各个长度下最优的“结尾最小值”从而保证了最终长度的正确性。这是一种“状态压缩”和“定义优化”的极致体现。6.4 从LIS到其他经典问题LIS的子问题分析模式可以迁移到许多其他问题上最大子数组和Maximum Subarraydp[i]定义为以nums[i]结尾的最大子数组和。状态转移dp[i] max(nums[i], dp[i-1] nums[i])。同样是“以i结尾”的定义。最长公共子序列LCS子问题定义为dp[i][j]表示字符串A[0..i]和B[0..j]的LCS长度。状态转移需要考虑字符是否相等。编辑距离Edit Distance子问题定义为dp[i][j]表示将单词A[0..i]转换为B[0..j]所需的最少操作数。它们的共性在于都通过一个精巧的状态定义通常是二维如LCS、编辑距离将原问题分解为规模更小的子问题并通过状态转移方程建立起子问题之间的联系。7. 实战心得如何训练“子问题分析”的肌肉记忆最后分享几点我个人在学习和教学DP时的体会这些是书本和标准题解里不会写的“软经验”。7.1 从“记忆”到“推导”不要一上来就背“dp数组定义”和“状态转移方程”。对于每一道新题强迫自己拿出一张白纸从问题描述开始尝试自己定义子问题。问自己我最关心什么信息什么样的子问题规模更小且结构相同这个子问题的解能否帮助我解决更大的问题这个过程一开始会很慢甚至会走错路就像我们对比了LIS的几种定义思路但这是形成DP直觉的唯一途径。走错路然后修正比直接走对路学到的东西更多。7.2 重视“手动模拟”在得出状态转移方程后不要急着写代码。一定要找一个小的、非平凡的实例比如长度5-6的数组手动模拟整个dp数组的填充过程。这个过程能帮你验证方程的正确性逻辑推导可能隐藏着边界错误手动算一遍能立刻发现。理解表的含义看着dp[i]一个个被算出来你会对“状态”和“转移”有更感性的认识。调试的预演如果代码出错你手算的表格就是最可靠的对照标准。7.3 思考“如果我是计算机”这是理解DP“自底向上”填表法的好方法。想象你是一台只能进行简单计算和记忆的机器。你有一个表格dp数组。你被问到dp[5]是多少。你不知道但你知道规则dp[5]取决于dp[0]到dp[4]以及它们对应的数字大小。所以你只好从dp[0]开始根据初始条件比如dp[0]1把它填上。然后根据dp[0]和规则去填dp[1]依此类推。这个过程就是动态规划的计算过程——从小问题开始逐步解决大问题并记住所有子问题的解以避免重复计算。7.4 对比“递归记忆化搜索”动态规划的递推写法自底向上填表和递归加记忆化搜索自顶向下是等价的只是思考方向不同。对于某些问题从原问题出发思考“要解决这个问题需要先解决哪些子问题”这种递归的思路可能更自然。例如在LIS中可以定义函数dfs(i)返回以i结尾的LIS长度其内部会递归调用dfs(j)j i。然后用一个数组memo存储dfs(i)的结果避免重复计算。这两种方法本质是一体两面都体现了“重叠子问题”和“最优子结构”。初学者可以都尝试实现加深理解。动态规划的精髓不在于记住多少个模板而在于掌握这种“定义子问题-建立联系-高效求解”的思维模式。LIS作为一个入门案例几乎包含了DP的所有核心概念。把它吃透再去看背包、区间DP、状态压缩DP你会发现它们都是在这个基本范式上的扩展和变形。子问题分析就是打开动态规划大门的钥匙而练习是让这把钥匙变得好用的唯一方法。