动态规划入门到实战：状态设计、转移方程与背包区间树形模型-北京尧图网络

动态规划这四个字几乎是每个写代码的人绕不过去的一道坎。我第一次真正被它按在地上摩擦是很多年前一场笔试的下午题目不难一串数字求最大不降子序列长度我信心满满写了个递归本地跑小数据全对提交之后大样例直接超时屏幕上的运行时间从毫秒跳到秒那一刻我才意识到自己写的不是“解法”只是一个把同一件事重复算了无数遍的暴力。后来我带过几批新人发现大家卡住的地方惊人地一致不是不会写循环而是不知道状态该定义成什么、转移该往哪个方向写、数组该开多大、初值该填几。这篇文章就围绕这些真实的卡点展开把动态规划从“玄学”拆成可以照着做的步骤它是什么、为什么有效、状态怎么定、方程怎么推、背包和区间树形这些经典模型各自在练什么、以及我在实际调试中反复踩到的那些坑。不管你是刚学完递归的新手还是能背出背包模板但一换题就懵的中级选手下面这些内容应该都能对上你的某一段经历。1. 动态规划到底在救什么场一次递归超时的现场还原先从最朴素的地方讲起因为动态规划的所有威力都来自它对“重复计算”的识别与消灭。很多人学DP的第一课是斐波那契觉得太简单没必要看但恰恰是这个最简单的例子把动态规划的两条主线——最优子结构和重叠子问题——暴露得最清楚。理解了这个你后面看背包、看区间合并才会有“哦原来还是这一套”的感觉而不是每道题都当成新知识死记。1.1 重复子问题是怎么被悄悄放大的写一个求第 n 项斐波那契的递归代码三行就能搞定def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)看着很干净但它的调用次数是指数级增长的。原因在于算 fib(5) 要算 fib(4) 和 fib(3)而算 fib(4) 时又要把 fib(3) 再算一遍fib(3) 又被 fib(2) 需要……同一批子问题被反复求解递归树里大量节点是完全重复的。n 稍微大一点比如 n40函数调用次数就上亿了这就是当年我超时的真正原因。这里的“重叠子问题”指的就是这个现象不同的求解路径会汇聚到同一个子问题上。动态规划做的第一件事就是把每个子问题的答案记下来下次遇到直接查表不再重算。这个动作叫记忆化它把指数级的调用次数压到了线性级——因为每个 n 只会被真正计算一次。你可以把递归树画出来把重复的节点用同一种颜色标上会非常直观地看到树的大部分体积都是重复的剪掉之后剩下的那部分就是动态规划真正要处理的工作量。1.2 记忆化搜索和递推填表是同一件事的两种写法把上面的递归加上缓存就得到了记忆化搜索def fib(n, memo): if n 1: return n if memo[n] ! -1: return memo[n] memo[n] fib(n - 1, memo) fib(n - 2, memo) return memo[n]而把它改成从前往后填数组就是递推def fib(n): if n 1: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这两段代码在数学上是等价的区别只在计算顺序记忆化是“需要什么算什么”自顶向下递推是“从小到大挨个算”自底向上。我一般建议新手先用记忆化把思路写通因为它离暴力递归最近改造成本低不容易一开始就卡在遍历顺序上等思路稳定了再改写成递推顺手做空间优化。这里有个我踩过的坑上面记忆化版本里 memo 千万不要写成函数的默认参数memo{}默认参数在函数定义时只创建一次多次调用会共享同一个字典测试用例之间互相污染本地单测能过、连着跑就错排查起来非常难受。正确做法是把 memo 作为参数显式传入或者在函数内部新建。1.3 不是所有题都能用DP无后效性才是通行证动态规划能用的前提除了最优子结构和重叠子问题还有一条经常被忽略的“无后效性”一旦某个状态确定后面怎么决策都不会再回头影响它。换句话说状态必须包含“做出后续决策所需要的全部历史信息”。举个反例如果题目要求路径上不能出现重复节点那么“当前在哪”这个状态就不够了你还需要知道“已经走过哪些点”历史信息没被压缩进状态后效性就出现了这时候要么扩展状态比如状压要么换算法。很多人写DP写崩根子不在方程推错而在状态设计时漏掉了必要的历史维度。判断方法很简单问自己一句“只靠这几个状态量能不能唯一确定接下来的最优选择”如果不能说明状态不够如果能但维度太多导致数组开不下说明需要找等价压缩方式比如用“已选集合”压成二进制位。这个判断习惯比背十个模板都管用。2. 状态怎么定、方程怎么写把“感觉”变成可验证的步骤新手最常问的一句话是“这题的状态怎么想出来的”。老实说状态设计确实带点经验成分但它不是纯灵感而是有一套可以照着走的推导流程。我在实际做题和给别人讲题时基本都按同一套顺序推进先明确“最后一步在做什么”再倒推出子问题最后用变量把子问题描述出来。这套流程不能保证一次就对但能保证你每次都有明确的起点卡住时也知道该回头改哪一块。2.1 状态定义要满足的三条硬标准一个好的状态定义我通常用三条标准去检验。第一可区分不同的状态必须对应不同的局面不能出现两个本质不同的情况被塞进同一个下标。第二可转移当前状态的最优值必须能由若干个更小状态的已知值推导出来推导过程不依赖尚未计算的东西。第三可枚举状态的取值范围是有限的、能开成数组或哈希表的不然你连表都填不了。拿“最长不降子序列”举例如果定义dp[i]为“前 i 个元素里的最长不降子序列长度”这个定义就违反了可转移性——因为以第 i 个元素结尾和不以它结尾是两种完全不同的情况混在一起没法推出下一步。正确做法是定义dp[i]为“以第 i 个元素结尾的最长不降子序列长度”这样转移时只需要枚举它前面的元素 j判断a[j] a[i]即可。你看状态定义差一个字可转移性就从无到有了。状态定义是否可转移问题所在dp[i] 表示前 i 个元素的最优值否结尾元素不确定无法接续dp[i] 表示以第 i 个元素结尾的最优值是结尾固定可枚举前驱dp[i][j] 表示前 i 个中选 j 个的最优值是维度清晰但要注意容量含义2.2 从“最后一步”倒推转移方程转移方程的推导我的习惯是从最后一步开始问到达这个状态的最后一步可能是什么动作把所有可能的最后动作枚举出来每一个动作对应一个更小的子问题取最优即可。以“爬楼梯”为例到达第 i 阶的最后一步要么是从 i-1 跨一步上来的要么是从 i-2 跨两步上来的于是dp[i] dp[i-1] dp[i-2]方程几乎是自然长出来的。再看“零钱兑换”凑出金额 i 的最后一步一定是用了某一枚面额为 c 的硬币那么dp[i] min(dp[i - c] 1)把 c 枚举一遍就行。这个方法的价值在于它把“凭空想公式”变成了“枚举最后动作”而最后动作的种类通常是有限的、可以穷举的。如果枚举完之后发现某个动作对应的子问题不好表示那就说明状态定义还需要加维度这是一个非常明确的修改信号而不是让你在原地干瞪眼。我见过不少人卡在方程上半小时其实就是没做这个枚举动作一直在凭记忆套模板。2.3 遍历顺序错了方程再对也白搭方程写对只是第一步填表的顺序同样致命。原则只有一条计算当前状态时它依赖的所有状态必须已经算好。线性DP一般是从小下标往大下标推但到了二维、多维就很容易翻车。最典型的是0-1背包的一维写法外层枚举物品、内层枚举容量内层必须倒序原因我在下一节会详细拆。再看区间DP依赖的是更短的区间所以循环要按区间长度从短到长来写而不是按左端点从前往后。我调试DP时的第一反应就是打印依赖关系把当前状态依赖哪些状态列出来对照循环顺序看有没有“用到未来值”的情况十有八九的错误都能在这一步被抓出来。如果实在理不清就老老实实写记忆化搜索让递归自己决定计算顺序等逻辑验证无误后再改递推——这也是我给新人的一条实用建议先求对再求快。3. 背包问题的谱系一维数组背后的维度坍缩背包是动态规划里最经典也最容易背错的一族。很多人能把一维模板默写出来却说不清为什么0-1背包要倒序、完全背包要正序结果一遇到多重背包或者分组背包就原形毕露。我的看法是背包问题的核心不在代码而在“每个物品能被选几次”这个语义以及一维数组在压缩时到底丢掉了什么信息。把这两点想通背包这一族基本就通了剩下的只是细节变体。3.1 0-1背包倒序枚举容量的真正原因先看二维版本的原始定义dp[i][j]表示考虑前 i 个物品、容量为 j 时能获得的最大价值转移是“不选第 i 个”或者“选第 i 个”dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])注意右边用的是dp[i-1]也就是上一轮的结果这保证了每个物品只被用一次。现在把它压成一维dp[j]代码变成for i in range(1, n 1): for j in range(capacity, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])内层为什么必须倒序因为正序时dp[j - w[i]]可能在本轮已经被更新过它里面已经包含了第 i 个物品再用它去更新dp[j]等于第 i 个物品被选了两次这就退化成了完全背包。倒序则保证dp[j - w[i]]取到的还是上一轮的值物品只用一次。这个解释我讲过很多遍但真正让人记住的是自己动手改成正序跑一遍看看答案是不是变大、变大后是不是恰好等于“每个物品都能无限拿”的结果。亲手验证过一次比背十遍口诀都牢。3.2 完全背包正序枚举与“物品无限”的语义对应完全背包每件物品可以拿任意多次一维写法就是把内层循环改成正序for i in range(1, n 1): for j in range(w[i], capacity 1): dp[j] max(dp[j], dp[j - w[i]] v[i])正序时dp[j - w[i]]是本轮已更新的值天然允许同一物品被重复叠加这正好对应“无限件”的语义。还有一个常被忽略的等价写法外层枚举容量、内层枚举物品这种写法在完全背包下也是对的但在0-1背包下就错了——因为0-1背包必须保证“一轮只决策一个物品”。这个细节说明循环顺序不是风格问题而是语义问题。我在带人时会让对方用一张小表手动模拟三个物品、容量为5的过程把每一步 dp 数组的值写下来肉眼看着数字怎么变化比看代码注释有效得多。3.3 多重背包二进制拆分与单调队列两条路多重背包每件物品有数量上限最直观的做法是把第 i 件物品拆成 c 个独立物品然后跑0-1背包复杂度是 O(n·C·Σc)数据一大就顶不住。常用优化是二进制拆分把数量 c 拆成 1、2、4、8… 以及最后剩下的余数这些“打包物品”的任意组合能表示 0 到 c 之间的任何数量于是复杂度降到 O(n·C·log c)。代码上就是把拆出来的每一包当成一个0-1物品处理。如果数据规模还要更狠就得上单调队列优化把内层按“模 w 的余数”分组用滑动窗口维护最大值把复杂度压到 O(n·C)。单调队列这一块理解成本偏高我的建议是先把二进制拆分写熟遇到真正卡时间的题再补单调队列不要一上来就啃最难的版本容易劝退。下面这个表可以帮你快速选路物品数量限制推荐写法时间复杂度每件最多1个0-1背包容量倒序O(n·C)每件无限个完全背包容量正序O(n·C)每件有上限 c二进制拆分O(n·C·log c)每件上限很大且数据紧单调队列优化O(n·C)3.4 分组背包与依赖背包语义一变循环顺序就变分组背包要求每组内最多选一个写法是外层枚举组、中层枚举容量、内层枚举组内物品注意中层和内层的顺序不能反否则会出现同组多选。依赖背包则更绕典型场景是“选某个物品前必须先选它的前置物品”这类问题一般是先把依赖关系建成树做一次树形DP把子树的结果合并成一个“组”再套分组背包。我处理这类题的顺序是先不管依赖把物品按树建好写出“以 u 为根的子树在容量 j 下的最大价值”然后在合并孩子时做一次分组背包式的枚举。这个套路在模拟项目里非常常见比如资源分配、权限包选择本质上都是带前置约束的背包。理解了“分组”和“依赖”只是给背包加了结构约束就不会觉得它们是全新的东西。4. 当问题有了结构区间DP与树形DP的建模套路线性DP处理的是“一条线”上的决策但现实里的问题经常带着结构一串相邻元素要合并、一棵树上的节点要选或不选。这时候状态的定义方式要跟着结构走循环的推进方式也要从“按下标递增”改成“按区间长度递增”或者“按后序遍历”。这一节的两个模型我觉得是动态规划从“会写”到“会用”的分水岭。4.1 区间DP枚举分割点按长度推进区间DP的典型场景是“相邻合并”一排石子每次只能合并相邻两堆合并的代价是两堆之和问把全部合并成一堆的最小总代价。状态定义为dp[l][r]表示把区间 [l, r] 合并成一堆的最小代价转移是枚举最后一次合并的分割点 kfor length in range(2, n 1): for l in range(0, n - length 1): r l length - 1 dp[l][r] INF for k in range(l, r): dp[l][r] min(dp[l][r], dp[l][k] dp[k1][r] cost(l, r))这里最关键的是最外层必须按区间长度从小到大枚举因为dp[l][r]依赖的两个子区间都比它短长度更小的必须先算完。如果按左端点从前往后写就会出现“用到一个还没算的区间”的情况结果要么是错的值要么是初始的极大值而且这种错误非常隐蔽小样例可能照样过。环形的区间问题比如环形石子合并处理办法是把数组复制一份接到末尾长度开到 2n最后在所有长度为 n 的区间里取最优。这个“断环成链”的技巧我建议直接记住它不只用于区间DP很多环形数组问题都能这么绕过去。4.2 树形DP后序遍历保证孩子先算完树形DP的状态一般挂在节点上比如dp[u][0/1]表示以 u 为根的子树里u 选或不选时的最优值。转移发生在“把孩子的结果合并到父亲”这一步所以计算顺序必须是后序遍历先递归处理所有孩子孩子算完了再更新父亲。最经典的模型是“树上最大独立集”父子不能同时选那么dp[u][0] sum(max(dp[v][0], dp[v][1]) for v in children) dp[u][1] val[u] sum(dp[v][0] for v in children)第一行表示 u 不选孩子选不选都行取大的第二行表示 u 选孩子必须不选。写递归时要注意递归深度链状树在 Python 里很容易触发递归上限实际项目中我会改成显式栈或者手动设置递归深度避免线上跑着跑着抛异常。另一个常见坑是根的选择无根树要随便指定一个根然后建双向边、递归时传入父节点防止走回头路这个parent参数漏掉就会无限递归调试时表现为栈溢出别问我怎么知道的。4.3 换根DP二次扫描解决“每个点都要算一遍”有些题要求对每个节点都求出“以它为根时的某个值”比如所有节点到它的距离之和。朴素做法是每个点跑一次DFS复杂度 O(n²)数据一大就废。换根DP的思路是先任选一个根算出答案再利用父子之间的递推关系把答案“推”到相邻节点。设down[u]为 u 的子树内节点到 u 的距离和sz[u]为子树大小先自底向上求出这两个值然后自顶向下做第二次扫描从父亲 u 推到孩子 v 时v 的答案等于 u 的答案加上“不在 v 子树里的节点数”再减去“在 v 子树里的节点数”也就是ans[v] ans[u] (n - sz[v]) - sz[v]这个式子的直觉是换根之后v 子树内的 sz[v] 个节点距离各减少 1其余 n - sz[v] 个节点距离各增加 1。第一次扫描求子树信息第二次扫描推全局答案这套“两遍DFS”的模板在模拟项目里出现过好几次比如计算网络节点的平均通信距离、评估某个中心点位置的合理性。它的难点不在代码而在于把“换根后距离如何变化”这件事想清楚建议在纸上画三个节点的链手动算一遍比看公式快。5. 状态压缩与数位DP把“集合”和“数位”塞进状态里有些问题的状态不是“前 i 个”这么简单而是“已经选了哪些”或者“前若干位填了什么”。这类问题的状态维度天然爆炸必须想办法压缩表示。状态压缩DP和数位DP就是两套成熟的压缩思路前者把集合压成二进制整数后者把数字的构造过程按位拆开。它们的共同点是状态的“形状”变了但推转移的那套流程没变。5.1 状压DP用二进制位表示选择集合当元素个数在 20 左右时可以用一个整数的二进制位表示“某个元素选没选”第 i 位为 1 表示选中。这样dp[mask]就能表示“在选中集合为 mask 的情况下的最优值”。最典型的应用是旅行商类问题dp[mask][i]表示已经访问过 mask 这些点、当前停在 i 点的最小花费转移是枚举下一个没访问的点 jfor mask in range(1 n): for i in range(n): if not (mask i) 1: continue for j in range(n): if (mask j) 1: continue dp[mask | (1 j)][j] min( dp[mask | (1 j)][j], dp[mask][i] dist[i][j] )位运算的几个常用操作要熟练mask (mask - 1)去掉最低位的1mask -mask取出最低位的1mask | (1 i)设置第 i 位(mask i) 1判断第 i 位。状压DP的复杂度通常是 O(2^n · n²)n 超过 22 基本就别想了所以看到题目数据范围在 15 到 20 之间就要条件反射地考虑状压。另一个常见用途是棋盘覆盖类问题用一行的选择状态作为 mask逐行转移这类题的难点在于判断两行状态是否兼容通常用位与运算就能快速判断。5.2 数位DP从高位到低位的前缀构造数位DP用来统计“在某个区间内满足某种数位条件的数有多少个”比如不含连续相同数字、数位和能被某个数整除。套路是把区间 [L, R] 转成 [0, R] 减去 [0, L-1]然后从高位往低位逐位填状态里带上“是否贴着上界”“前一位是什么”“当前数位和”等信息def dfs(pos, tight, last, started): if pos len(digits): return 1 if started else 0 if not tight and memo[pos][last][started] ! -1: return memo[pos][last][started] limit digits[pos] if tight else 9 total 0 for d in range(0, limit 1): total dfs(pos 1, tight and d limit, d, started or d ! 0) if not tight: memo[pos][last][started] total return total这里tight表示当前是否还贴着上界只有不贴的时候才能记忆化因为贴边状态只出现一次记了也没用。started用来处理前导零避免把 000123 里的前导零当成真实的数位。数位DP的模板很固定真正花时间的是把题目条件翻译成状态参数比如“相邻两位差的绝对值不小于2”就在转移时多判断一下比如“数位和模 m 为 0”就在状态里加一维余数。我的经验是先把状态参数列成表写清楚每个参数的含义和取值范围再去写递归比边写边想靠谱得多。5.3 复杂度估算别被状态数骗了写完DP一定要养成估算复杂度的习惯。状态数乘以转移代价就是大致的时间。比如状压DP是 2^n × n 个状态每个状态枚举 n 个后继就是 O(2^n · n²)区间DP是 O(n²) 个状态每个状态枚举 O(n) 个分割点就是 O(n³)数位DP的状态数通常是“位数 × 上一位取值 × 余数”之类的乘积再乘以每位的枚举量。这个习惯能帮你在写代码前就发现“这题按这个状态设计肯定会超时”从而及时换思路。我见过不少人代码写完、样例过了、提交超时才开始回头想复杂度这时候改动的成本已经很高了。反过来如果算出来复杂度在可接受范围内但常数偏大就可以提前考虑用数组代替字典、用滚动数组压维、把内层循环里重复计算的部分提到外面这些小优化在数据紧的时候往往就是过与不过的分界线。6. 实测中反复踩的坑初始化、溢出与常数优化算法思路对代码也写出来了结果还是错这种时候问题通常出在“边角料”上。我把这些年调试DP时最常遇到的三类问题整理出来它们不涉及高深理论但每一个都能让正确答案变成错误答案而且往往在小数据上不暴露一上大数据就原形毕露。6.1 初始值的三种典型错误第一类是求最小值时把 dp 数组初始化成 0。求最小值的题初值应该是无穷大否则min(0, 某个正数)永远是 0答案直接变成 0 或者一个不可能达到的值。第二类是求最大值时初值给得太小导致加法溢出或者结果被截断处理办法是用一个足够大的负数表示“不可达”并且在转移时判断来源是否可达。第三类是边界条件漏初始化比如背包问题里dp[0] 0表示容量为 0 时价值为 0这一句漏掉整个数组就全是无效值。我的一般做法是先把“不可能状态”统一赋成一个哨兵值然后在转移时显式判断“如果来源是哨兵就跳过”这样即使某个状态不可达也不会污染后续计算。下面这张对照表可以贴在显示器边上场景正确初值常见错误求最小代价无穷大dp[0]0全部初始化为 0求最大价值负无穷或 -1 表示不可达全 0 导致非法状态被当成合法计数方案数dp[0]1其余 0忘记 dp[0]1结果全 0布尔可达性Falsedp[0]True只初始化部分边界6.2 方案数取模与答案溢出计数类DP经常要求对一个大质数取模麻烦在于取模的位置。如果只在最后取一次模中间结果可能早就溢出特别是在 Python 以外的语言里长整型也会被撑爆如果每一步都取模又要小心减法之后出现负数。我的习惯是加法转移每一步都取模减法转移取模后加一个模数再取模乘法转移如果两个因子都小于模数乘完立刻取模。另外取模不影响比较大小的题千万不要乱取模比如“求最大值”的题取模之后大小关系就乱了这类错误我在review别人的代码时见过不止一次表现为答案忽大忽小、毫无规律。6.3 常数优化滚动数组、预处理和剪枝空间上最常用的优化是滚动数组。如果dp[i]只依赖dp[i-1]就可以把第一维压掉用两个变量或者一个长度为 2 的数组轮换如果依赖的是固定窗口还可以用循环数组。背包的一维写法本质上就是滚动数组的应用。时间上预处理能省掉大量重复计算比如区间DP里的区间和提前用前缀和算好内层就不用每次都循环求和再比如状压DP里的距离矩阵提前算好存起来比在转移里现算快得多。剪枝方面枚举顺序很关键把更容易产生最优解的分支放在前面配合“当前值已经不可能优于已知最优解就跳过”的判断实测能省下可观的常数时间。这些优化单独看都不起眼但在数据规模卡在临界点时往往就是它们决定了能不能过。最后分享一个我自己的习惯每写完一道DP不管过没过都手动构造一组极小数据把 dp 表打印出来一格一格对照手算结果。这个过程很笨但它能让你真正看见状态是怎么一步步被填满的哪一格填错了、哪一步依赖了还没算的值一眼就能看出来。我最早学DP的那段时间就是靠这个笨办法把背包的倒序、区间DP的长度推进、树形DP的后序遍历一个个啃下来的比看任何讲解都扎实。后来带新人也一样让他们自己打印一遍比我在旁边讲半小时管用。动态规划这东西看懂和写对之间隔着一段必须亲手填表的路谁也绕不过去。

动态规划入门到实战：状态设计、转移方程与背包区间树形模型

相关推荐

VASPKIT 0.72 配置与VASP输入文件生成避坑指南

Cloudflare OS实战：边缘计算平台架构设计与应用开发指南

可信计算线上测试复习：PCR、EK/AK与远程证明实战拆解

更多资讯

AI Agent技能体系：从玩具到生产力工具的关键设计

agent-skills：可组合、可验证、可演进的智能体能力单元

agent-skills：可组合、可验证的智能体技能契约设计

光伏电站智能管理系统：物联网与大数据技术的应用实践

STM32 ST-Link V2-37-26 驱动安装与稳定烧录指南

FrameFetch：开源视频剧本对齐与AI分析报告工具

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？