尧图网站开发 
1. 项目概述从“最优”的直觉到“动态规划”的框架在解决很多实际问题时我们常常会遇到这样一种情况一个大的决策过程可以分解成一系列前后关联的小决策。比如你要规划一个为期一周的旅行每天选择去哪个景点不仅要考虑当天的乐趣还要考虑交通衔接、体力分配最终目标是让整周的体验“最优”。又比如一个项目有多个阶段每个阶段都有多种资源分配方案如何选择才能在总预算内让项目总收益最大这类问题的一个核心特征就是“最优子结构”——整个问题的最优解包含了其子问题的最优解。而动态规划就是处理这类具有“重叠子问题”和“最优子结构”性质问题的利器。它不是某种具体的算法而是一种思想一种方法论。你可以把它理解为一个“聪明的穷举”策略。普通的穷举把所有可能性都试一遍计算量爆炸。动态规划则通过记住已经解决过的子问题的答案专业术语叫“记忆化”或“填表”避免重复计算从而将指数级复杂度降为多项式级。这次我们就来彻底拆解动态规划从最经典的“背包问题”和“最长上升子序列”入手把它的核心思想、解题步骤、代码实现以及那些容易踩的坑一次讲透。无论你是正在备战数学建模竞赛还是单纯对算法优化感兴趣这篇内容都能让你从“知道概念”升级到“能手撕代码”。2. 动态规划的核心思想与解题框架拆解2.1 思想内核最优子结构与重叠子问题动态规划能奏效依赖于问题的两个关键性质缺一不可。最优子结构这是动态规划的“灵魂”。它意味着问题的最优解可以由其子问题的最优解有效地构造出来。举个例子从北京到广州的最短路径如果经过武汉那么这条路径中“北京到武汉”这一段也必须是北京到武汉的所有可能路径中最短的那条。如果子问题的最优解无法组合成原问题的最优解那动态规划就无从谈起。在建模时我们首先要问自己大问题的最优解和小问题的最优解之间是否存在这种递推关系重叠子问题这是动态规划的“效率源泉”。在递归求解的过程中同一个子问题会被反复计算多次。比如在计算斐波那契数列F(5)时F(3)会被计算多次。动态规划通过将子问题的解存储起来记忆化当再次需要时直接查表从而避免了大量重复计算。如果子问题完全不重叠比如归并排序虽然也有最优子结构但用分治法就够了动态规划的优势体现不出来。注意很多初学者容易混淆“分治法”和“动态规划”。两者都涉及分解问题。关键区别在于分治法分解出的子问题通常是独立的如归并排序的左半部分和右半部分而动态规划的子问题是重叠的。可以简单记子问题独立用分治子问题重叠用动规。2.2 通用解题五步法面对一个陌生问题如何判断能否用动态规划解决又该如何入手我总结了一个五步心法亲测有效。第一步定义状态最重要也是最难的一步状态就是描述问题某个阶段情况的“快照”。我们需要用一组参数通常是数组下标来定义这个状态。定义的状态要能唯一确定一个子问题并且要足够简洁。常见的状态定义有dp[i]表示以第i个元素结尾的某种最优解。dp[i][j]表示在处理到前i个物品且容量/限制为j时的最优解。更复杂的可能需要三维甚至带状态压缩。第二步确定状态转移方程核心推导这是建立子问题与大问题之间递推关系的公式。通常形式是dp[当前状态] 最优 (dp[之前状态1] 代价1, dp[之前状态2] 代价2, ...)。找到这个方程问题就解决了一大半。思考方向往往是“要到达当前状态有哪些可能的上一状态从每个上一状态转移过来需要什么代价哪个选择是最优的”第三步初始化基础状态任何递推都需要起点。我们需要给最小、最基础的子问题通常是边界情况赋予确定的值。比如dp[0]或dp[0][0]应该等于多少。初始化错误会导致整个结果链出错。第四步确定计算顺序填表顺序为了保证在计算当前状态时它所依赖的“之前状态”都已经被计算并存储好了我们必须确定一个正确的计算顺序。可能是从左到右、从上到下、斜对角线顺序甚至是拓扑排序顺序。第五步返回最终结果最终答案不一定就是dp[n]可能是dp数组中的最大值、最小值或者某个特定状态的值。需要根据问题具体分析。3. 经典案例深度剖析01背包与最长上升子序列理论说再多不如看两个最经典的例子。我们分别用自顶向下记忆化搜索和自底向上递推填表两种方式来实现你会对动态规划有更立体的理解。3.1 案例一01背包问题每个物品最多选一次问题描述有一个容量为C的背包和N个物品。第i个物品的重量为weight[i]价值为value[i]。每个物品要么完整放入1要么不放入0。问在不超过背包容量的前提下能装入物品的最大总价值是多少第一步定义状态最直观的状态定义是dp[i][c]表示考虑前i个物品物品编号从1到N在背包容量恰好为c时所能获得的最大价值。实操心得这里定义“恰好容量为c”有时不如“容量不超过c”方便。但“恰好”的定义在后续某些变种问题如装满背包的方案数中更严谨。初学者可以先采用“不超过”的定义dp[i][c]表示考虑前i个物品在背包容量不超过c时的最大价值。这样初始化会更简单全部为0。第二步推导状态转移方程对于每个物品i和每种容量c我们有两种选择不放入物品 i那么最大价值就是考虑前i-1个物品、容量为c时的最大价值即dp[i-1][c]。放入物品 i前提是当前背包容量c weight[i]。放入后背包剩余容量为c - weight[i]价值增加value[i]。那么最大价值就是dp[i-1][c - weight[i]] value[i]。我们的目标是价值最大所以在这两种选择中取最大值dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])其中第二个选项仅在c weight[i]时有效。第三步初始化当物品数量为0时 (i0)无论容量多大最大价值都是0。即dp[0][:] 0。 当背包容量为0时 (c0)无论有多少物品都无法放入任何东西最大价值也是0。即dp[:][0] 0。第四步计算顺序显然dp[i][...]依赖于dp[i-1][...]所以i需要从1到N递增计算。对于每个ic可以从1到C递增计算因为dp[i][c]可能依赖于dp[i-1][c - weight[i]]c-weight[i]比c小只要c从小到大算依赖的状态必然已经算好。第五步返回结果最终答案就是dp[N][C]表示考虑所有N个物品背包容量不超过C时的最大价值。代码实现自底向上递推def knapsack_01(weights, values, capacity): N len(weights) # dp[i][c] 初始化 (N1) x (capacity1) 的二维数组 dp [[0] * (capacity 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 w, v weights[i-1], values[i-1] # 注意下标对齐 for c in range(1, capacity 1): # 遍历容量 if c w: # 当前容量装不下物品i dp[i][c] dp[i-1][c] else: # 装得下选择装或不装的最大值 dp[i][c] max(dp[i-1][c], dp[i-1][c - w] v) return dp[N][capacity] # 示例 weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 8 print(knapsack_01(weights, values, capacity)) # 输出10 (选择物品1和4)空间优化滚动数组观察状态转移方程dp[i][...]只依赖于dp[i-1][...]。这意味着我们不需要保存整个二维数组只需要一个一维数组dp[c]然后在遍历容量时从后往前更新即可。从后往前是为了保证在更新dp[c]时dp[c - w]还是上一轮 (i-1) 的值没有被本轮覆盖。def knapsack_01_optimized(weights, values, capacity): dp [0] * (capacity 1) N len(weights) for i in range(N): w, v weights[i], values[i] # 关键容量从大到小遍历 for c in range(capacity, w - 1, -1): dp[c] max(dp[c], dp[c - w] v) return dp[capacity]避坑技巧01背包的空间优化写法中内层循环必须从大到小遍历容量。如果是完全背包物品无限个内层循环才需要从小到大遍历。这个顺序搞反是背包问题最经典的错误。3.2 案例二最长上升子序列LIS问题描述给定一个整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续。第一步定义状态一种直接的状态定义是dp[i]表示以第i个数字结尾的最长上升子序列的长度。 为什么这么定义因为这样定义后dp[i]的值可以由它前面的状态dp[j] (j i)推导出来满足了最优子结构。第二步推导状态转移方程如何求dp[i]对于位置i我们需要遍历它之前的所有位置j (0 j i)。 如果nums[i] nums[j]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的上升子序列。 那么dp[i]就等于所有满足条件的dp[j]中的最大值再加1加上nums[i]自己。 即dp[i] max(dp[j]) 1, 对于所有 j i 且 nums[j] nums[i]。 如果不存在这样的j即nums[i]比前面所有数都小那么以nums[i]结尾的LIS就是它自己长度为1。第三步初始化每个位置至少可以以自己结尾长度至少为1。所以初始化dp数组全为1。第四步计算顺序由于dp[i]依赖于所有j i的dp[j]所以i从0到n-1顺序遍历即可。对于每个i内层需要遍历0到i-1。第五步返回结果最终答案不是dp[n-1]因为最长上升子序列不一定以最后一个元素结尾。答案是整个dp数组中的最大值。代码实现O(n²) 动态规划def 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[i] nums[j]: 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)) # 输出4 (子序列 [2, 5, 7, 101] 或 [2, 5, 7, 18])更优解法O(n log n) 贪心二分查找对于LIS问题存在一种更高效的算法。其核心思想是维护一个tails数组tails[k]表示长度为k1的所有上升子序列中结尾元素最小的那个值。这个数组本身是递增的。遍历原数组对于每个数num如果num比tails中所有数都大就把它 append 到末尾表示发现了更长的LIS。否则在tails中找到第一个大于等于num的数用num替换它。这一步可以用二分查找所以是 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) # 延长LIS else: tails[left] num # 替换保证同长度下结尾元素最小 return len(tails) # tails的长度就是LIS的长度注意事项tails数组存储的并不一定是真实的LIS它只保证了长度是正确的。如果需要输出具体的LIS序列通常还是需要用 O(n²) 的DP并记录前驱节点来回溯。在数学建模中如果只求长度优先考虑 O(n log n) 的算法效率提升巨大。4. 动态规划的常见变体与建模技巧掌握了经典模型我们来看看动态规划如何应对更复杂的情况。建模的关键在于状态定义的灵活性。4.1 状态定义的扩展维度很多问题不是一维或二维状态就能解决的需要增加维度来记录更多信息。带维度的状态比如“股票买卖”系列问题状态中除了天数还需要记录持有股票的状态0表示未持有1表示持有以及交易次数限制。状态可能定义为dp[i][k][0 or 1]。区间DP状态通常定义为dp[i][j]表示区间[i, j]上的最优解。常用于处理回文串、石子合并等问题。计算顺序往往是先枚举区间长度再枚举起点。状态压缩DP当状态中的某个维度是“集合”或“排列”时比如旅行商问题中已经访问过的城市集合可以用一个整数的二进制位来表示从而将状态压缩到一维数组。这是动态规划中比较高级的技巧。4.2 背包问题的家族背包问题是动态规划的“黄埔军校”其变种极多完全背包每件物品有无限个。与01背包的唯一区别是在状态转移时dp[i][c]可以依赖于dp[i][c - w]因为物品i可以重复选取。代码实现上只需将01背包空间优化后的内层循环从从大到小改为从小到大遍历容量。多重背包每件物品有固定的数量count[i]。最朴素的想法是将其拆分成count[i]个01背包物品但这样效率低。优化方法有二进制拆分将数量拆分成1,2,4,...2^k, remainder 的组合转化为01背包或单调队列优化。分组背包物品被分为若干组每组内物品互斥最多只能选一个。解决方法是在最外层遍历组内层遍历容量最内层遍历组内物品保证每组只选一个。依赖背包树形DP物品间存在依赖关系如“选儿子必须先选父亲”。这通常需要结合树形结构进行递归DP。4.3 路径与坐标型DP这类问题通常在一个网格中进行状态dp[i][j]表示到达坐标(i, j)的最优解如最小路径和、不同路径数。状态转移通常只依赖于上方和左方的格子dp[i][j] f(dp[i-1][j], dp[i][j-1])。初始化时需要特别注意第一行和第一列。5. 实战避坑指南与调试技巧动态规划的代码写出来容易写对难。下面是我在无数次调试中总结出的血泪经验。5.1 常见错误类型与排查表错误现象可能原因排查方法结果输出为0或初始值1. 状态转移方程逻辑错误根本没更新。2. 初始化错误基础状态设为了0导致递推不出结果。3. 最终结果取错了位置如取了dp[0]。1. 打印整个dp表看递推过程是否如预期更新。2. 检查边界条件i0,j0等的初始化值。3. 确认问题要求的最终答案对应哪个状态。结果比预期小1. 状态转移时max取成了min或反之。2. 在状态转移中漏掉了某种可能的选择。3. 数组下标越界导致访问了非法内存在一些语言中可能返回0。1. 仔细审题明确是求最大值还是最小值。2. 重新推导状态转移方程列举所有可能的前置状态。3. 在访问数组前增加条件判断或使用调试器查看。结果比预期大1. 同一个子问题的贡献被重复计算了多次。2. 在完全背包问题中使用了01背包的遍历顺序反之亦然。1. 检查状态定义是否唯一确定了子问题是否存在歧义。2.重点检查循环顺序特别是空间优化后的版本。内存超限DP表维度太大。例如n10^5,C10^5二维数组dp[n][C]会爆内存。考虑空间优化滚动数组或者重新审视问题看状态维度能否减少例如价值如果范围小可以用价值作为维度求最小重量。时间超限状态数太多或每个状态转移的代价太高。O(n³) 的算法对于 n1000 就可能超时。1. 优化状态转移例如用前缀和、单调队列、斜率优化等降低复杂度。2. 重新设计状态减少维度。5.2 调试与验证心法从小样例开始不要一上来就用复杂的大数据。先用题目给的示例甚至自己构造一个n3或n4的极小样例手动推导出正确答案然后用你的程序跑看结果是否一致。打印DP表这是最直观的调试手段。将计算过程中的dp数组完整打印出来与你手动推导的表格进行逐项对比。不一致的地方就是bug所在。关注边界i0,j0,c0这些边界情况是初始化最容易出错的地方。单独测试这些情况。对比暴力搜索对于小规模数据n 20可以写一个暴力搜索DFS来枚举所有可能解与你的DP结果对比。这是验证DP正确性的“金标准”。理解而非记忆不要死记硬背“背包九讲”的模板。理解每个状态、每个转移、每个循环顺序的物理意义。问自己“这个循环顺序为什么是对的反过来为什么不行” 只有理解了才能应对千变万化的题目。5.3 数学建模中的应用要点在数学建模竞赛中动态规划常用于资源分配、生产调度、最优路径规划等问题。此时难点往往不在于写出DP方程而在于将实际问题抽象为模型识别出什么是“阶段”时间、步骤什么是“状态”资源存量、位置什么是“决策”选择哪种方案以及“指标函数”要最大化或最小化的目标。处理连续状态实际问题中的状态如资金、时间可能是连续的而计算机需要离散化。需要合理确定离散化的粒度在精度和计算量之间权衡。状态空间爆炸即使离散化后状态数量也可能极其庞大。这时需要考虑剪枝、启发式搜索如A*算法与DP结合或者用近似算法。输出方案不仅要求最优值还要求最优解的具体方案。这需要在DP过程中记录“决策”或“前驱状态”最后通过回溯来构造方案。通常的做法是再用一个与dp数组同维度的pre数组在状态转移时如果发生了更新就记录下是从哪个状态转移过来的。动态规划的魅力在于它将一个看似复杂无比的大问题分解成一系列有逻辑关联的小问题并通过“记忆”避免了重复劳动。掌握它就像获得了一把解决最优化问题的万能钥匙。核心永远是那五步定义状态、写出方程、初始化、确定顺序、获取答案。剩下的就是在大量练习中积累对不同问题模型的敏感度以及调试时的那份耐心。当你面对一个新问题能自信地开始设计dp数组时你就真正入门了。 
1. 项目概述从“最优”的直觉到“动态规划”的框架在解决很多实际问题时我们常常会遇到这样一种情况一个大的决策过程可以分解成一系列前后关联的小决策。比如你要规划一个为期一周的旅行每天选择去哪个景点不仅要考虑当天的乐趣还要考虑交通衔接、体力分配最终目标是让整周的体验“最优”。又比如一个项目有多个阶段每个阶段都有多种资源分配方案如何选择才能在总预算内让项目总收益最大这类问题的一个核心特征就是“最优子结构”——整个问题的最优解包含了其子问题的最优解。而动态规划就是处理这类具有“重叠子问题”和“最优子结构”性质问题的利器。它不是某种具体的算法而是一种思想一种方法论。你可以把它理解为一个“聪明的穷举”策略。普通的穷举把所有可能性都试一遍计算量爆炸。动态规划则通过记住已经解决过的子问题的答案专业术语叫“记忆化”或“填表”避免重复计算从而将指数级复杂度降为多项式级。这次我们就来彻底拆解动态规划从最经典的“背包问题”和“最长上升子序列”入手把它的核心思想、解题步骤、代码实现以及那些容易踩的坑一次讲透。无论你是正在备战数学建模竞赛还是单纯对算法优化感兴趣这篇内容都能让你从“知道概念”升级到“能手撕代码”。2. 动态规划的核心思想与解题框架拆解2.1 思想内核最优子结构与重叠子问题动态规划能奏效依赖于问题的两个关键性质缺一不可。最优子结构这是动态规划的“灵魂”。它意味着问题的最优解可以由其子问题的最优解有效地构造出来。举个例子从北京到广州的最短路径如果经过武汉那么这条路径中“北京到武汉”这一段也必须是北京到武汉的所有可能路径中最短的那条。如果子问题的最优解无法组合成原问题的最优解那动态规划就无从谈起。在建模时我们首先要问自己大问题的最优解和小问题的最优解之间是否存在这种递推关系重叠子问题这是动态规划的“效率源泉”。在递归求解的过程中同一个子问题会被反复计算多次。比如在计算斐波那契数列F(5)时F(3)会被计算多次。动态规划通过将子问题的解存储起来记忆化当再次需要时直接查表从而避免了大量重复计算。如果子问题完全不重叠比如归并排序虽然也有最优子结构但用分治法就够了动态规划的优势体现不出来。注意很多初学者容易混淆“分治法”和“动态规划”。两者都涉及分解问题。关键区别在于分治法分解出的子问题通常是独立的如归并排序的左半部分和右半部分而动态规划的子问题是重叠的。可以简单记子问题独立用分治子问题重叠用动规。2.2 通用解题五步法面对一个陌生问题如何判断能否用动态规划解决又该如何入手我总结了一个五步心法亲测有效。第一步定义状态最重要也是最难的一步状态就是描述问题某个阶段情况的“快照”。我们需要用一组参数通常是数组下标来定义这个状态。定义的状态要能唯一确定一个子问题并且要足够简洁。常见的状态定义有dp[i]表示以第i个元素结尾的某种最优解。dp[i][j]表示在处理到前i个物品且容量/限制为j时的最优解。更复杂的可能需要三维甚至带状态压缩。第二步确定状态转移方程核心推导这是建立子问题与大问题之间递推关系的公式。通常形式是dp[当前状态] 最优 (dp[之前状态1] 代价1, dp[之前状态2] 代价2, ...)。找到这个方程问题就解决了一大半。思考方向往往是“要到达当前状态有哪些可能的上一状态从每个上一状态转移过来需要什么代价哪个选择是最优的”第三步初始化基础状态任何递推都需要起点。我们需要给最小、最基础的子问题通常是边界情况赋予确定的值。比如dp[0]或dp[0][0]应该等于多少。初始化错误会导致整个结果链出错。第四步确定计算顺序填表顺序为了保证在计算当前状态时它所依赖的“之前状态”都已经被计算并存储好了我们必须确定一个正确的计算顺序。可能是从左到右、从上到下、斜对角线顺序甚至是拓扑排序顺序。第五步返回最终结果最终答案不一定就是dp[n]可能是dp数组中的最大值、最小值或者某个特定状态的值。需要根据问题具体分析。3. 经典案例深度剖析01背包与最长上升子序列理论说再多不如看两个最经典的例子。我们分别用自顶向下记忆化搜索和自底向上递推填表两种方式来实现你会对动态规划有更立体的理解。3.1 案例一01背包问题每个物品最多选一次问题描述有一个容量为C的背包和N个物品。第i个物品的重量为weight[i]价值为value[i]。每个物品要么完整放入1要么不放入0。问在不超过背包容量的前提下能装入物品的最大总价值是多少第一步定义状态最直观的状态定义是dp[i][c]表示考虑前i个物品物品编号从1到N在背包容量恰好为c时所能获得的最大价值。实操心得这里定义“恰好容量为c”有时不如“容量不超过c”方便。但“恰好”的定义在后续某些变种问题如装满背包的方案数中更严谨。初学者可以先采用“不超过”的定义dp[i][c]表示考虑前i个物品在背包容量不超过c时的最大价值。这样初始化会更简单全部为0。第二步推导状态转移方程对于每个物品i和每种容量c我们有两种选择不放入物品 i那么最大价值就是考虑前i-1个物品、容量为c时的最大价值即dp[i-1][c]。放入物品 i前提是当前背包容量c weight[i]。放入后背包剩余容量为c - weight[i]价值增加value[i]。那么最大价值就是dp[i-1][c - weight[i]] value[i]。我们的目标是价值最大所以在这两种选择中取最大值dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])其中第二个选项仅在c weight[i]时有效。第三步初始化当物品数量为0时 (i0)无论容量多大最大价值都是0。即dp[0][:] 0。 当背包容量为0时 (c0)无论有多少物品都无法放入任何东西最大价值也是0。即dp[:][0] 0。第四步计算顺序显然dp[i][...]依赖于dp[i-1][...]所以i需要从1到N递增计算。对于每个ic可以从1到C递增计算因为dp[i][c]可能依赖于dp[i-1][c - weight[i]]c-weight[i]比c小只要c从小到大算依赖的状态必然已经算好。第五步返回结果最终答案就是dp[N][C]表示考虑所有N个物品背包容量不超过C时的最大价值。代码实现自底向上递推def knapsack_01(weights, values, capacity): N len(weights) # dp[i][c] 初始化 (N1) x (capacity1) 的二维数组 dp [[0] * (capacity 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 w, v weights[i-1], values[i-1] # 注意下标对齐 for c in range(1, capacity 1): # 遍历容量 if c w: # 当前容量装不下物品i dp[i][c] dp[i-1][c] else: # 装得下选择装或不装的最大值 dp[i][c] max(dp[i-1][c], dp[i-1][c - w] v) return dp[N][capacity] # 示例 weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 8 print(knapsack_01(weights, values, capacity)) # 输出10 (选择物品1和4)空间优化滚动数组观察状态转移方程dp[i][...]只依赖于dp[i-1][...]。这意味着我们不需要保存整个二维数组只需要一个一维数组dp[c]然后在遍历容量时从后往前更新即可。从后往前是为了保证在更新dp[c]时dp[c - w]还是上一轮 (i-1) 的值没有被本轮覆盖。def knapsack_01_optimized(weights, values, capacity): dp [0] * (capacity 1) N len(weights) for i in range(N): w, v weights[i], values[i] # 关键容量从大到小遍历 for c in range(capacity, w - 1, -1): dp[c] max(dp[c], dp[c - w] v) return dp[capacity]避坑技巧01背包的空间优化写法中内层循环必须从大到小遍历容量。如果是完全背包物品无限个内层循环才需要从小到大遍历。这个顺序搞反是背包问题最经典的错误。3.2 案例二最长上升子序列LIS问题描述给定一个整数数组nums找到其中最长严格递增子序列的长度。子序列不要求连续。第一步定义状态一种直接的状态定义是dp[i]表示以第i个数字结尾的最长上升子序列的长度。 为什么这么定义因为这样定义后dp[i]的值可以由它前面的状态dp[j] (j i)推导出来满足了最优子结构。第二步推导状态转移方程如何求dp[i]对于位置i我们需要遍历它之前的所有位置j (0 j i)。 如果nums[i] nums[j]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的上升子序列。 那么dp[i]就等于所有满足条件的dp[j]中的最大值再加1加上nums[i]自己。 即dp[i] max(dp[j]) 1, 对于所有 j i 且 nums[j] nums[i]。 如果不存在这样的j即nums[i]比前面所有数都小那么以nums[i]结尾的LIS就是它自己长度为1。第三步初始化每个位置至少可以以自己结尾长度至少为1。所以初始化dp数组全为1。第四步计算顺序由于dp[i]依赖于所有j i的dp[j]所以i从0到n-1顺序遍历即可。对于每个i内层需要遍历0到i-1。第五步返回结果最终答案不是dp[n-1]因为最长上升子序列不一定以最后一个元素结尾。答案是整个dp数组中的最大值。代码实现O(n²) 动态规划def 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[i] nums[j]: 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)) # 输出4 (子序列 [2, 5, 7, 101] 或 [2, 5, 7, 18])更优解法O(n log n) 贪心二分查找对于LIS问题存在一种更高效的算法。其核心思想是维护一个tails数组tails[k]表示长度为k1的所有上升子序列中结尾元素最小的那个值。这个数组本身是递增的。遍历原数组对于每个数num如果num比tails中所有数都大就把它 append 到末尾表示发现了更长的LIS。否则在tails中找到第一个大于等于num的数用num替换它。这一步可以用二分查找所以是 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) # 延长LIS else: tails[left] num # 替换保证同长度下结尾元素最小 return len(tails) # tails的长度就是LIS的长度注意事项tails数组存储的并不一定是真实的LIS它只保证了长度是正确的。如果需要输出具体的LIS序列通常还是需要用 O(n²) 的DP并记录前驱节点来回溯。在数学建模中如果只求长度优先考虑 O(n log n) 的算法效率提升巨大。4. 动态规划的常见变体与建模技巧掌握了经典模型我们来看看动态规划如何应对更复杂的情况。建模的关键在于状态定义的灵活性。4.1 状态定义的扩展维度很多问题不是一维或二维状态就能解决的需要增加维度来记录更多信息。带维度的状态比如“股票买卖”系列问题状态中除了天数还需要记录持有股票的状态0表示未持有1表示持有以及交易次数限制。状态可能定义为dp[i][k][0 or 1]。区间DP状态通常定义为dp[i][j]表示区间[i, j]上的最优解。常用于处理回文串、石子合并等问题。计算顺序往往是先枚举区间长度再枚举起点。状态压缩DP当状态中的某个维度是“集合”或“排列”时比如旅行商问题中已经访问过的城市集合可以用一个整数的二进制位来表示从而将状态压缩到一维数组。这是动态规划中比较高级的技巧。4.2 背包问题的家族背包问题是动态规划的“黄埔军校”其变种极多完全背包每件物品有无限个。与01背包的唯一区别是在状态转移时dp[i][c]可以依赖于dp[i][c - w]因为物品i可以重复选取。代码实现上只需将01背包空间优化后的内层循环从从大到小改为从小到大遍历容量。多重背包每件物品有固定的数量count[i]。最朴素的想法是将其拆分成count[i]个01背包物品但这样效率低。优化方法有二进制拆分将数量拆分成1,2,4,...2^k, remainder 的组合转化为01背包或单调队列优化。分组背包物品被分为若干组每组内物品互斥最多只能选一个。解决方法是在最外层遍历组内层遍历容量最内层遍历组内物品保证每组只选一个。依赖背包树形DP物品间存在依赖关系如“选儿子必须先选父亲”。这通常需要结合树形结构进行递归DP。4.3 路径与坐标型DP这类问题通常在一个网格中进行状态dp[i][j]表示到达坐标(i, j)的最优解如最小路径和、不同路径数。状态转移通常只依赖于上方和左方的格子dp[i][j] f(dp[i-1][j], dp[i][j-1])。初始化时需要特别注意第一行和第一列。5. 实战避坑指南与调试技巧动态规划的代码写出来容易写对难。下面是我在无数次调试中总结出的血泪经验。5.1 常见错误类型与排查表错误现象可能原因排查方法结果输出为0或初始值1. 状态转移方程逻辑错误根本没更新。2. 初始化错误基础状态设为了0导致递推不出结果。3. 最终结果取错了位置如取了dp[0]。1. 打印整个dp表看递推过程是否如预期更新。2. 检查边界条件i0,j0等的初始化值。3. 确认问题要求的最终答案对应哪个状态。结果比预期小1. 状态转移时max取成了min或反之。2. 在状态转移中漏掉了某种可能的选择。3. 数组下标越界导致访问了非法内存在一些语言中可能返回0。1. 仔细审题明确是求最大值还是最小值。2. 重新推导状态转移方程列举所有可能的前置状态。3. 在访问数组前增加条件判断或使用调试器查看。结果比预期大1. 同一个子问题的贡献被重复计算了多次。2. 在完全背包问题中使用了01背包的遍历顺序反之亦然。1. 检查状态定义是否唯一确定了子问题是否存在歧义。2.重点检查循环顺序特别是空间优化后的版本。内存超限DP表维度太大。例如n10^5,C10^5二维数组dp[n][C]会爆内存。考虑空间优化滚动数组或者重新审视问题看状态维度能否减少例如价值如果范围小可以用价值作为维度求最小重量。时间超限状态数太多或每个状态转移的代价太高。O(n³) 的算法对于 n1000 就可能超时。1. 优化状态转移例如用前缀和、单调队列、斜率优化等降低复杂度。2. 重新设计状态减少维度。5.2 调试与验证心法从小样例开始不要一上来就用复杂的大数据。先用题目给的示例甚至自己构造一个n3或n4的极小样例手动推导出正确答案然后用你的程序跑看结果是否一致。打印DP表这是最直观的调试手段。将计算过程中的dp数组完整打印出来与你手动推导的表格进行逐项对比。不一致的地方就是bug所在。关注边界i0,j0,c0这些边界情况是初始化最容易出错的地方。单独测试这些情况。对比暴力搜索对于小规模数据n 20可以写一个暴力搜索DFS来枚举所有可能解与你的DP结果对比。这是验证DP正确性的“金标准”。理解而非记忆不要死记硬背“背包九讲”的模板。理解每个状态、每个转移、每个循环顺序的物理意义。问自己“这个循环顺序为什么是对的反过来为什么不行” 只有理解了才能应对千变万化的题目。5.3 数学建模中的应用要点在数学建模竞赛中动态规划常用于资源分配、生产调度、最优路径规划等问题。此时难点往往不在于写出DP方程而在于将实际问题抽象为模型识别出什么是“阶段”时间、步骤什么是“状态”资源存量、位置什么是“决策”选择哪种方案以及“指标函数”要最大化或最小化的目标。处理连续状态实际问题中的状态如资金、时间可能是连续的而计算机需要离散化。需要合理确定离散化的粒度在精度和计算量之间权衡。状态空间爆炸即使离散化后状态数量也可能极其庞大。这时需要考虑剪枝、启发式搜索如A*算法与DP结合或者用近似算法。输出方案不仅要求最优值还要求最优解的具体方案。这需要在DP过程中记录“决策”或“前驱状态”最后通过回溯来构造方案。通常的做法是再用一个与dp数组同维度的pre数组在状态转移时如果发生了更新就记录下是从哪个状态转移过来的。动态规划的魅力在于它将一个看似复杂无比的大问题分解成一系列有逻辑关联的小问题并通过“记忆”避免了重复劳动。掌握它就像获得了一把解决最优化问题的万能钥匙。核心永远是那五步定义状态、写出方程、初始化、确定顺序、获取答案。剩下的就是在大量练习中积累对不同问题模型的敏感度以及调试时的那份耐心。当你面对一个新问题能自信地开始设计dp数组时你就真正入门了。