1. 从“傻算”到“聪明算”为什么我们需要动态规划如果你刷过算法题或者接触过一些稍微复杂的编程问题大概率会听过“动态规划”这四个字。它常常和“困难”、“面试必考”、“思路巧妙”这些标签绑在一起让不少初学者望而生畏。但今天我想从一个最朴素的角度带你重新理解动态规划。它不是什么高深莫测的魔法而是一种源于我们本能却又被我们忽视的“聪明”计算方式。想象一个最简单的场景计算斐波那契数列的第n项。它的定义是F(0)0, F(1)1, F(n)F(n-1)F(n-2)。最直观的写法是什么递归。def fib(n): if n 1: return n return fib(n-1) fib(n-2)这段代码清晰、正确符合数学定义。但如果你试着计算fib(40)甚至fib(50)你会明显感觉到程序的“卡顿”。为什么因为它在进行大量重复的、无意义的计算。为了计算fib(5)程序的计算树是这样的fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) ...你可以看到fib(3)被计算了2次fib(2)被计算了3次fib(1)和fib(0)被计算的次数更是呈指数级增长。当n变大时这种重复计算的开销是灾难性的。这种一个问题的子问题被重复计算多次的现象就是动态规划第一个核心思想的来源重叠子问题。我们的本能是“遇到问题直接求解”。但动态规划教会我们的是先别急着算看看要算的东西是不是之前已经算过了如果算过了直接拿过来用。这就像你解一道复杂的数学题其中需要多次用到sin(30°)的值。一个“傻”的学生会每次重新推导或计算而一个“聪明”的学生会第一次算好后把结果0.5记在草稿纸的角落后面需要时直接看一眼就用。动态规划就是让计算机学会这种“记笔记”的聪明方法。那么仅仅把重复计算的结果存起来就行了吗这就是第二个关键最优子结构。它说的是一个大规模问题的最优解可以由其小规模子问题的最优解组合得到。比如你想找到从北京到上海的最短路径。如果这条最短路径经过南京那么从北京到南京的这段子路径也一定是北京到南京所有可能路径中的最短路径同样南京到上海那段也是最短的。不可能存在一条整体最短的路径其中某一段却不是最短的。这个性质保证了我们可以通过先解决“从北京到南京最短”和“从南京到上海最短”这两个子问题然后组合它们来得到原问题的最优解。如果一个问题不具备最优子结构动态规划就无从谈起。例如求一张图中最长的简单路径不允许重复经过节点。即使你知道了从A到B的最长路径和从B到C的最长路径把它们拼起来未必是A到C的最长路径因为拼起来的路径可能会经过重复的节点。因此最长路径问题就没有最优子结构通常不能用动态规划高效解决。所以动态规划的本质是利用“重叠子问题”的冗余性来减少计算量而“最优子结构”则提供了将大问题分解为小问题并组合求解的理论基础。它把指数级的时间复杂度通过“空间换时间”记录子问题解的策略降低到了多项式级别。接下来我们就深入这两个核心概念的细节看看它们如何具体指导我们设计和实现算法。2. 重叠子问题识别与量化计算冗余重叠子问题是动态规划适用的必要条件也是其提升效率的根本所在。但“重叠”二字听起来有点抽象我们如何具体识别一个问题是否存在重叠子问题又如何量化这种重叠带来的计算冗余呢2.1 识别重叠子问题递归树与状态空间最直观的方法是画出递归树就像我们为斐波那契数列做的那样。如果递归树中有大量相同的节点代表相同的子问题那么重叠子问题就存在。更一般地我们可以从“状态”的角度来思考。动态规划解决的是多阶段决策问题每个“状态”代表了问题在某个特定时刻的“快照”。以经典的爬楼梯问题为例你每次可以爬1阶或2阶楼梯问爬到第n阶有多少种不同的方法。我们定义状态dp[i]为“爬到第i阶楼梯的方法数”。那么要到达第i阶你只能从第i-1阶爬1步上来或者从第i-2阶爬2步上来。因此dp[i] dp[i-1] dp[i-2]。如果我们用递归求解dp[n]def climb(i): if i 2: return i # dp[1]1, dp[2]2 return climb(i-1) climb(i-2)计算climb(5)的递归树中climb(3)会被计算多次。这里的“状态”就是楼梯的阶数i。不同的递归调用参数i如果相同就对应同一个子问题。因为i的取值范围是有限的0到n所以子问题的总数是O(n)个但递归调用却产生了指数级的计算量这中间的差值就是重叠子问题导致的浪费。注意重叠子问题不一定意味着递归解法一定低效。如果每个子问题只被计算常数次那么递归也是高效的。动态规划针对的是那些子问题被重复计算指数次、多项式次的场景。2.2 量化冗余从指数到多项式的跃迁让我们量化一下斐波那契数列递归算法的浪费程度。朴素递归的时间复杂度是O(2^n)因为递归树近似一棵深度为n的二叉树。而实际上我们只需要计算F(0), F(1), ..., F(n)这n1个不同的值。如果我们能“记住”这些结果每个值只算一次那么时间复杂度可以立刻降到O(n)。这个从O(2^n)到O(n)的跃迁就是解决重叠子问题带来的巨大收益。这种“记住”结果的技术就是记忆化搜索它本质是递归缓存。我们开一个数组memo初始化为一个特殊值如-1表示未计算。def fib_memo(n, memo): if n 1: return n if memo[n] ! -1: # 如果已经计算过直接返回 return memo[n] memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) # 计算并存储 return memo[n] # 初始化备忘录 n 40 memo [-1] * (n1) print(fib_memo(n, memo))记忆化搜索是“自顶向下”的我们从目标问题fib(n)开始递归地分解子问题遇到算过的就直接返回。这是理解重叠子问题最自然的实现方式。2.3 重叠的典型模式与误区不是所有有递归关系的问题都有显著的重叠子问题。关键在于状态参数是否会在不同的递归路径中取到相同的值。典型模式序列/区间问题如最长上升子序列、最长公共子序列。状态通常定义为dp[i]以i结尾或dp[i][j]区间i到j。在递归求解dp[i][j]时其中间状态dp[k][l]会被多个不同的父问题用到。背包问题状态定义为dp[i][v]考虑前i件物品容量为v时的最大价值。当尝试不同物品组合时相同的(i, v)状态会被反复到达。路径问题在网格中从左上角到右下角只能向右或向下走求路径总数。状态dp[i][j]到达(i,j)的路径数会被其上方和左方的格子多次依赖。常见误区“这个问题看起来可以分解所以能用DP”错。必须验证是否存在重叠子问题。比如二叉树的最大深度虽然可以递归分解深度 max(左子树深度, 右子树深度) 1但每个子树都是全新的问题没有重叠因此用DP没有优势递归足矣。“重叠子问题就是递归”不完全对。递归是描述问题分解的方式重叠子问题是这种分解方式下表现出来的一种现象或性质。动态规划是利用这种性质进行优化的方法。识别出重叠子问题我们就找到了应用动态规划优化算法的突破口。接下来我们需要确保这种分解和组合是有效的这就是最优子结构要回答的问题。3. 最优子结构保证分解组合的有效性如果说重叠子问题告诉我们“可以省力”那么最优子结构就告诉我们“省力的方法是对的”。它是动态规划能够正确求解最优化问题的基石。3.1 定义与直观理解最优子结构性质官方定义是一个问题的最优解包含其子问题的最优解。换句话说我们可以通过组合子问题的最优解来构造原问题的最优解。这个定义有点绕我们用一个非技术的例子来理解假设你要组装一台性价比最高的电脑预算是1万元。你决定先选CPU再选显卡最后用剩余预算配其他部件。你的策略是在某个价位段选择一款性能最强的CPU然后基于剩下的预算选择一款性能最强的显卡最后用最后的预算搭配其他部件。这个策略成功的前提是——“在总预算固定下性价比最高的整机配置必然包含了在子预算如CPU预算下的性价比最高的CPU选择”。如果这个前提不成立比如有时为了整体平衡可能需要牺牲一点CPU性能去换一个更好的显卡那么你的“分步最优”策略就得不到全局最优解。此时该问题就不具备最优子结构。在算法中0-1背包问题是最经典的例子。给定物品重量w[i]、价值v[i]和背包容量C每个物品最多选一个求最大总价值。我们定义状态dp[i][c]为考虑前i个物品在背包容量为c时能获得的最大价值。对于第i个物品我们有两种选择不放入背包那么最优价值就是考虑前i-1个物品、容量为c时的最优价值即dp[i-1][c]。放入背包前提是c w[i]那么最优价值是“第i个物品的价值v[i]”加上“考虑前i-1个物品、剩余容量为c-w[i]时的最优价值”即v[i] dp[i-1][c-w[i]]。状态转移方程是dp[i][c] max(dp[i-1][c], v[i] dp[i-1][c-w[i]])。这个方程成立的关键在于最优子结构dp[i][c]这个“大问题”的最优解确实是从dp[i-1][c]和dp[i-1][c-w[i]]这两个“子问题”的最优解中产生的。我们不需要考虑dp[i-1][c]或dp[i-1][c-w[i]]具体是怎么来的只需要知道它们存储的就是对应子问题的最优值即可。3.2 验证最优子结构反证法的思路如何验证一个问题是否具有最优子结构一个实用的思路是反证法。假设问题P的最优解S包含子问题P1的解S1。我们假设S1不是子问题P1的最优解那么必然存在P1的另一个解S1比S1更优。如果我们用S1替换掉S中的S1就能得到一个对于原问题P更好的解S。但这与S是P的最优解矛盾。因此假设不成立S1必须是P1的最优解。以前面的爬楼梯问题为例虽然它是计数问题但逻辑类似。假设到达第5阶的最优最多方法序列是S。S的最后一步要么是从第4阶跨1步要么是从第3阶跨2步。假设S的最后一步是从第4阶跨上来的那么S中到达第4阶的那部分子序列S1必须是到达第4阶的最多方法序列。如果存在另一个到达第4阶的方法序列S1比S1更多那么用S1加上最后一步就能得到一个到达第5阶的、比S更多的方法序列这与S是最优解矛盾。3.3 不具备最优子结构的例子最长简单路径我们之前提到的最长简单路径问题是经典的反例。考虑下图A --(1)-- B --(1)-- C \ / \--(2)-- D --(2)/假设边权代表距离求从A到C的最长简单路径。显然最长路径是 A-D-C长度为4。这条路径经过了D。现在看子问题从A到D的最长简单路径是 A-B-C-D 吗注意简单路径不允许重复节点。路径 A-B-C-D 是合法的长度为3。但是在全局最优解 A-D-C 中从A到D的部分仅仅是直接边 A-D长度为2。这里全局最优解A-D-C并没有使用子问题A到D的最优解A-B-C-D长度为3。因为如果使用了子问题的最优解 A-B-C-D路径为A,B,C,D那么再加上边 D-C 就会形成 A,B,C,D,C节点C重复了这不是一条简单路径。因此最长简单路径问题不具备最优子结构。3.4 与贪心算法的区别贪心算法也要求最优子结构但它的要求更苛刻贪心算法要求每一步都做出一个局部最优选择并且这个局部最优选择能导向全局最优解。它通常不需要考虑所有子问题而是基于某种排序或规则直接做出选择。动态规划则不同它考虑了所有可能的子问题并通过比较这些子问题组合的结果来得到最优解。在0-1背包问题中动态规划会显式地比较“不放物品i”和“放物品i”这两种子问题组合。而如果背包问题允许物品分割分数背包那么贪心算法按价值密度排序后依次拿取就能得到最优解因为此时局部最优拿当前密度最高的能保证全局最优。理解最优子结构能帮助我们在面对新问题时快速判断动态规划是否是一个可行的思路。一旦确认了重叠子问题和最优子结构我们就可以着手设计动态规划的具体解法了。4. 动态规划的两种实现范式自顶向下与自底向上理解了核心概念我们来看看如何将它们转化为代码。动态规划主要有两种实现方式它们各有优劣适用于不同场景。4.1 自顶向下记忆化搜索这种方式最符合人类的自然思维。我们从一个完整的、规模较大的问题开始“顶”递归地将它分解成更小的子问题。为了避免重复计算我们使用一个备忘录通常是数组或哈希表来存储已经解决过的子问题的答案。算法步骤定义递归函数参数是子问题的状态表示。在函数开头检查备忘录中是否已有该状态的解。如果有直接返回。如果是基础情况最小子问题直接计算并返回结果。否则根据状态转移方程递归调用函数求解更小的子问题利用这些结果计算当前问题的解。将计算结果存入备忘录然后返回。以斐波那契数列的记忆化搜索为例def fib_top_down(n, memo): # 基础情况 if n 1: return n # 查备忘录 if memo[n] ! -1: return memo[n] # 递归求解并保存 memo[n] fib_top_down(n-1, memo) fib_top_down(n-2, memo) return memo[n] n 50 memo [-1] * (n1) result fib_top_down(n, memo)优点思路直观代码几乎就是状态转移方程的直译易于理解和调试。按需计算只计算实际被递归调用到的子问题对于状态空间很大但实际触及状态不多的问题可以节省时间和空间。缺点递归开销递归调用有函数调用栈的开销对于深度很大的递归可能导致栈溢出。代码结构稍复杂需要显式维护备忘录和递归函数。4.2 自底向上递推填表这种方式更符合“动态规划”这个名字中的“规划”。我们从最小的、最基本的子问题开始“底”逐步构建更大规模问题的解直到解决原问题。通常使用一个多维数组DP表来存储所有子问题的解。算法步骤确定DP数组的定义及其维度。dp[i]或dp[i][j]代表什么状态下的最优值。确定边界条件基础情况并初始化DP数组。确定状态转移顺序即循环的嵌套顺序确保在计算dp[i][j]时它所依赖的子问题dp[i-1][j]、dp[i][j-1]等都已经计算完毕。编写循环根据状态转移方程填充DP表。DP表的最后一个元素或某个特定位置就是原问题的解。以斐波那契数列的递推为例def fib_bottom_up(n): if n 1: return n # 1. 定义并初始化DP数组 dp [0] * (n1) dp[0], dp[1] 0, 1 # 边界条件 # 2. 按顺序递推 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] # 状态转移 return dp[n]优点效率稳定通常有更小的常数因子避免了递归开销。空间优化潜力大很多时候我们不需要保存整个DP表只需保存前几个状态如斐波那契只需保存前两个可以将空间复杂度从 O(n) 降到 O(1)。易于分析DP表清晰地展示了所有子问题的解便于理解和验证。缺点需要确定计算顺序对于复杂的依赖关系如区间DP、树形DP确定正确的填表顺序可能是个挑战。可能计算多余状态会计算所有可能状态即使有些状态最终用不到。4.3 如何选择与经典问题对比选择建议初学者或问题复杂时优先考虑自顶向下记忆化搜索。它更安全不容易在状态转移顺序上出错。先把正确的递归关系写出来加上备忘录往往就能得到一个可用的DP解法。追求极致性能或进行空间优化时使用自底向上递推。当你对问题非常熟悉并且明确所有状态的依赖关系后递推写法通常更高效也更容易进行空间压缩。以“最长上升子序列”问题为例问题给定一个整数数组nums找到其中最长严格递增子序列的长度。自顶向下记忆化搜索思路定义函数dfs(i)表示以nums[i]结尾的最长上升子序列长度。def lengthOfLIS_top_down(nums): n len(nums) memo [-1] * n def dfs(i): if memo[i] ! -1: return memo[i] max_len 1 # 至少包含自己 for j in range(i): if nums[j] nums[i]: max_len max(max_len, dfs(j) 1) memo[i] max_len return max_len # 最终答案是所有 dfs(i) 中的最大值 return max(dfs(i) for i in range(n)) if n 0 else 0自底向上递推思路定义dp[i]表示以nums[i]结尾的最长上升子序列长度。def lengthOfLIS_bottom_up(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数组中的最大值可以看到递推的写法更简洁也更容易看出时间复杂度是 O(n²)。而记忆化搜索的递归结构更清晰地反映了“以i结尾”这个状态的定义。两种方式本质上都在解决相同的重叠子问题计算每个dp[i]时都需要用到前面所有dp[j]并依赖于最优子结构以i结尾的最长序列必然由某个更小的j结尾的最长序列加上i构成。5. 状态设计与转移方程动态规划的灵魂动态规划最难也最核心的部分就是设计“状态”和“状态转移方程”。状态定义决定了问题的视角和解的空间而转移方程描述了如何从小状态推导出大状态。这部分没有万能公式但有一些通用的思考模式和经典模型。5.1 状态设计的常见角度线性/序列模型单状态dp[i]通常表示以第i个元素结尾的某种最优解。最长上升子序列dp[i]表示以nums[i]结尾的最长上升子序列长度。最大子数组和dp[i]表示以nums[i]结尾的最大子数组和。双状态dp[i][0/1]常用于带有状态切换的问题如股票买卖、打家劫舍。打家劫舍dp[i][0]表示不偷第i间房时的最大金额dp[i][1]表示偷第i间房时的最大金额。前缀/区间模型dp[i][j]表示序列中从i到j的这个区间的最优解。最长回文子串dp[i][j]表示字符串s从i到j的子串是否是回文。矩阵链乘法dp[i][j]表示计算矩阵A[i]...A[j]所需的最小标量乘法次数。背包模型0-1背包dp[i][c]表示考虑前i个物品在容量为c的背包中能获得的最大价值。完全背包dp[i][c]表示考虑前i种物品每种无限个在容量为c的背包中能获得的最大价值。优化后常使用一维数组dp[c]。多维费用背包dp[i][c1][c2]限制条件不止一个如重量和体积。状态压缩DP当状态可以用一个集合表示且集合规模不大时如n 20可以用一个整数的二进制位来表示集合dp[mask]表示达到某种状态集合时的最优解。旅行商问题dp[mask][i]表示已经访问过的城市集合为mask且当前位于城市i时的最短路径。树形DP状态通常与树的节点相关在树上进行后序遍历先处理孩子再处理父亲。二叉树中的最大路径和需要设计两个状态node_gain从该节点向下延伸的最大路径和可作为父节点路径的一部分和全局维护的max_sum。5.2 推导状态转移方程状态转移方程是状态之间的递推关系。推导时可以问自己一个问题要得到当前状态dp[x]有哪些可能的“最后一步”操作这些操作分别依赖于哪些更小的子状态以“最大子数组和”为例状态定义dp[i]表示以第i个数字结尾的连续子数组的最大和。 思考以nums[i]结尾的子数组其“最后一步”就是是否将nums[i]接在前一个子数组后面。如果接上去能使和变大就接上dp[i] dp[i-1] nums[i]如果接上去反而更小即dp[i-1] 0那就从nums[i]重新开始dp[i] nums[i]因此转移方程为dp[i] max(nums[i], dp[i-1] nums[i])以“0-1背包”为例状态定义dp[i][c]表示考虑前i个物品容量为c时的最大价值。 思考对于第i个物品我们有两种选择最后一步决策不选那么最大价值就是考虑前i-1个物品、容量不变时的最大价值即dp[i-1][c]。选前提是c w[i]那么最大价值是“物品i的价值”加上“考虑前i-1个物品、剩余容量为c-w[i]时的最大价值”即v[i] dp[i-1][c-w[i]]。我们在两种决策中取最大值dp[i][c] max(dp[i-1][c], v[i] dp[i-1][c-w[i]])。5.3 初始化与边界处理初始化是动态规划正确运行的保证它对应着最小子问题基础情况的解。序列问题通常dp[0]需要单独初始化。例如最大子数组和dp[0] nums[0]。背包问题通常dp[0][...] 0考虑0个物品价值为0dp[...][0] 0容量为0价值为0。区间DP对角线dp[i][i]通常代表长度为1的区间需要初始化。涉及负索引或越界有时需要将DP数组开大一点或者对索引0的情况做特殊判断。例如在爬楼梯问题中dp[1]1, dp[2]2而dp[0]可以定义为1从地面到第0阶有一种方法这样dp[2] dp[1] dp[0] 112也成立使转移方程更统一。5.4 一个综合案例编辑距离编辑距离是状态设计的经典问题给定两个单词word1和word2计算将word1转换成word2所需的最少操作数。操作包括插入一个字符、删除一个字符、替换一个字符。状态设计dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数。这里i和j可以理解为“已经处理了多少字符”。转移方程推导考虑如何得到dp[i][j]即处理完word1前i个和word2前j个字符。如果word1[i-1] word2[j-1]注意下标从0开始所以是i-1和j-1那么最后一个字符相同不需要操作dp[i][j] dp[i-1][j-1]。如果最后一个字符不同我们有三种“最后一步”操作替换将word1的第i个字符替换成word2的第j个字符。操作后两者前i-1和j-1个字符需要匹配代价为dp[i-1][j-1] 1。删除删除word1的第i个字符。操作后word1的前i-1个字符需要匹配word2的前j个字符代价为dp[i-1][j] 1。插入在word1的第i个位置后插入word2的第j个字符。操作后word1的前i个字符新插入的字符已匹配需要匹配word2的前j-1个字符代价为dp[i][j-1] 1。取三者最小值dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1。初始化dp[0][j] j将空字符串转换为word2的前j个字符需要j次插入。dp[i][0] i将word1的前i个字符转换为空字符串需要i次删除。def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n1) for _ in range(m1)] # 初始化 for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j # 递推填表 for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1 return dp[m][n]这个例子完美展示了如何通过定义合适的状态dp[i][j]分析所有可能的最后一步操作从而推导出覆盖所有情况的状态转移方程。状态设计得好问题就解决了一半。6. 空间优化从二维表格到滚动数组在初步写出动态规划代码后我们经常会发现DP表占用了大量内存尤其是当状态维度较高时。这时空间优化技巧就派上用场了。最常用的技巧是滚动数组和降维。6.1 滚动数组只保留必要的历史状态观察许多动态规划的状态转移方程当前状态往往只依赖于有限的几个历史状态而不是整个历史表格。这时我们可以复用DP数组只保留计算当前状态所必需的那部分数据。经典例子斐波那契数列原始的DP数组是dp[0..n]。但dp[i]只依赖于dp[i-1]和dp[i-2]。我们完全不需要保存整个数组只需要两个变量滚动更新即可。def fib_optimized(n): if n 1: return n prev, curr 0, 1 # 分别代表 dp[i-2], dp[i-1] for i in range(2, n1): # 计算 dp[i] next_val prev curr # 滚动更新 prev, curr curr, next_val return curr空间复杂度从 O(n) 降到了 O(1)。更一般的二维滚动数组0-1背包原始的0-1背包状态转移是dp[i][c] max(dp[i-1][c], v[i] dp[i-1][c-w[i]])。可以看到第i行的状态只依赖于第i-1行的状态。因此我们不需要一个n x C的二维数组只需要一个一维数组dp[c]代表“当前考虑物品阶段”下各容量对应的最大价值。但这里有个关键点内层循环必须逆序从C到0。def knapsack_01(values, weights, capacity): n len(values) dp [0] * (capacity 1) for i in range(n): # 逆序枚举容量 for c in range(capacity, weights[i]-1, -1): dp[c] max(dp[c], values[i] dp[c - weights[i]]) return dp[capacity]为什么要逆序因为dp[c]更新时需要用到旧状态即上一轮循环对应i-1的dp[c - weights[i]]。如果正序更新当更新到dp[c]时dp[c - weights[i]]可能已经被本轮的更新覆盖了变成了i阶段的状态这就相当于同一件物品被多次放入变成了完全背包的逻辑。逆序更新保证了在计算dp[c]时dp[c - weights[i]]还是上一轮i-1阶段的值。6.2 完全背包的空间优化正序循环与0-1背包相反完全背包因为每种物品无限个所以在更新dp[c]时允许使用本轮已经更新过的dp[c - weights[i]]即已经考虑过再放入一个当前物品的情况。因此内层循环是正序的。def knapsack_complete(values, weights, capacity): n len(values) dp [0] * (capacity 1) for i in range(n): # 正序枚举容量 for c in range(weights[i], capacity1): dp[c] max(dp[c], values[i] dp[c - weights[i]]) return dp[capacity]这个区别是背包问题空间优化的核心务必理解其背后的原因。6.3 状态压缩DP用位运算表示集合对于状态是集合的问题如旅行商问题如果集合元素不超过20个可以用一个整数的二进制位来表示。第k位为1表示元素k在集合中。# 假设有n个城市求从城市0出发访问所有城市恰好一次并回到0的最短路径 def tsp(dist): n len(dist) # dp[mask][i] 表示访问过的城市集合为mask当前在城市i的最短路径长度 # 初始化一个很大的数 INF float(inf) dp [[INF] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发只访问了城市0当前在0路径长为0 for mask in range(1 n): for i in range(n): if dp[mask][i] INF: continue # 尝试从城市i去往下一个未访问的城市j for j in range(n): if mask (1 j) 0: # 城市j未访问 new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j]) # 最终状态所有城市都访问过(mask (1n)-1)且回到城市0 ans INF for i in range(1, n): # 从其他城市i回到0 ans min(ans, dp[(1 n) - 1][i] dist[i][0]) return ans这里mask就是一个状态压缩的整数1 n表示 2^n 种状态组合。空间复杂度从 O(n!) 降到了 O(n * 2^n)虽然仍然很大但对于 n20 是可行的。空间优化是动态规划进阶的必备技能。它不仅能减少内存占用有时还能让代码更简洁。但优化时一定要清楚状态之间的依赖关系确保更新顺序正确否则很容易引入难以察觉的错误。我的经验是先写出直观的、未优化的二维甚至三维DP确保正确性然后再思考如何优化空间。