动态规划这四个字很多学算法的朋友听到就头皮发麻。我当年第一次接触 DP也是这样——看别人把一道看起来毫无头绪的题三五行代码写完感觉自己整个人都不好了。后来啃了无数道题踩过无数次错状态定义和死循环的坑才慢慢摸出门道。今天这篇笔记就是想把我在实际刷题和带新人过程中积累下来的那套“动态规划操作手册”完整地写出来。先说清楚这篇内容是什么、能解决什么问题动态规划Dynamic Programming简称 DP是一类“用空间换时间”的算法思想解决的是一票“有重叠子问题 最优子结构”的优化问题比如最短路径、最长子序列、背包问题、路径计数、编辑距离甚至小到统计走路方案数、大到车辆动态规划问题里都会用到它。适合什么人读不管你是准备算法面试的工程师、要打蓝桥杯/ACM 的学生还是刚入门数据结构与算法、看到 DP 题就头大的新手这篇文章都能给你一套能直接抄作业的思考流程和排错清单。我保证不整那些虚头巴脑的源码分析就从最接地气的例子开始把我踩过的坑、总结出的判断方法、还有面试里高频出现的几个经典模型全部摊开来说。1. 动态规划到底是什么先打破几个误区1.1 它不是一门高深的学问而是“聪明的枚举”很多人第一次看到 DP 的题解会被状态转移方程吓住。其实你反过来想一切 DP 问题本质上都可以用暴力枚举算法写出来。枚举所有可能的方案再挑最优的答案一定是对的只是会慢到天荒地老。动态规划干的事就是把暴力枚举里重复计算的部分记下来下次直接用避免对同一个子问题反复解。所以它有个很朴素的一句话解释记忆化递归 自底向上打表。我用一个最经典的例子说明斐波那契数列。# 暴力递归 def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)你计算fib(5)的时候fib(3)会被算两次fib(2)会被算三次n 一大指数级爆炸。可你明明每次算完都知道答案了为什么还要重复算用一个数组存一下不就好了# 记忆化递归自顶向下 def fib(n, memo{}): if n in memo: return memo[n] if n 1: return n memo[n] fib(n - 1) fib(n - 2) return memo[n]这就是 DP 的雏形。所以别把 DP 当成什么玄学它就是暴力枚举的“去重优化版”。1.2 和暴力枚举、贪心、递归到底什么关系我面试的时候经常被问DP 和贪心有什么区别和递归又是什么关系先讲贪心。贪心算法是每一步都选当前看起来最优的不做回头路DP 是把所有选择都摆出来用状态转移统一比较。用生活类比你从家去公司贪心就是每一段路都挑当时绿灯最多的路口走可能最后反而绕远DP 是把所有可能路径都记录下来每到一个路口都保留“走到这里最少花多少时间”最后全局最优。递归是一种实现方式DP 是一种算法思想。记忆化递归是 DP 的自顶向下写法循环打表是 DP 的自底向上写法两种只是实现习惯不同核心逻辑完全一致。那“剪枝算法”呢搜索算法里剪枝是在搜索树上砍掉必不可能的子树DP 时不也要剪枝吗可以这么理解DP 的“剪枝”发生在状态转移的选择时刻——只保留每个状态的最优解把其他不可能成为答案的信息丢掉。这比搜索里靠边界条件剪枝要狠得多因为它是数学层面的压缩。1.3 什么时候该用 DP两个判断条件不是所有问题都能用 DP。我用一套判断口诀百试不爽最优子结构大问题的最优解能由子问题的最优解推出。比如走楼梯到第 n 层的最少步数一定是从第 n-1 层或第 n-2 层的最少步数加一步得到。如果大问题的最优解和子问题没关系DP 就别想了。重叠子问题同一个子问题会在大问题中反复出现。走楼梯里dp[3]会被dp[4]和dp[5]都用到这不就是重叠吗。满足这两个条件就能用 DP 把指数级的暴力枚举压缩成多项式复杂度。如果只满足最优子结构但不重叠用分治法更合适如果不要求全局最优贪心可能更快。我自己的习惯是拿到题先画递归树树里有重复节点就上 DP。2. 从零搭起 DP 思路状态、转移、边界与顺序2.1 状态定义把问题压缩成一张表DP 的第一步也是最容易卡住的一步就是定义dp[i]到底表示什么。我见过太多人转移方程写不出来不是数学不行而是状态定义得太模糊。状态定义的本质是找到一个维度把原问题按这个维度切成无数个子问题。比如“从起点走到第 n 阶台阶的方案数”i就是第几阶“前 i 件物品里选若干件总重量不超过 W 的最大价值”i和W就是两个维度。拿到一道题我建议你先问自己三个问题这个问题的输入有哪些可变的量问题规模可以按哪个/哪些参数缩小我最终想要的答案应该存在哪个状态里比如最长递增子序列问题LIS给定数组[10, 9, 2, 5, 3, 7, 101, 18]求最长递增子序列长度。可变参数就是“结尾位置”所以定义dp[i]为以nums[i]结尾的最长递增子序列长度。为什么非要强调“以第 i 个元素结尾”因为递增序列需要知道上一个元素是谁才好判断能不能接上去。2.2 状态转移方程从“如何走到这一步”反推状态定义好了转移方程就是“当前状态和前面状态的关系”。这一步的核心技巧是不要直接想 dp[i] 怎么算先想 dp[i] 是由哪些 dp[j] 推过来的。拿爬楼梯说到第 i 阶要么从第 i-1 阶跨一步要么从第 i-2 阶跨两步。所以dp[i] dp[i-1] dp[i-2]这个方程看着简单但它是判断你题目做得对不对的关键。LIS 的转移稍微复杂一点if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1)意思是如果第 j 个元素能接在第 i 个元素前面那以 i 结尾的 LIS 长度至少是以 j 结尾的长度加 1。把所有更小的 j 都尝试一遍取最大值。写转移方程的时候我强烈建议你旁边放一张草稿纸把前几个值手动算一遍。算到第三个值还符合直觉再动手写代码不然十有八九要返工。2.3 初始化和边界最容易翻车的地方初始化是 DP 里出错率最高的环节。很多人把dp数组全填 0 就开跑结果答案全是 0。我总结了一个初始化检查清单起点值dp[0]或dp[1]是不是已知的比如斐波那契dp[0]0, dp[1]1。取最值的方向求最小值时dp要初始化为一个很大的数比如float(inf)不然没被更新过的小数会污染答案求最大值时初始化为负无穷求方案数时初始化为 0。二维表的边界行/列比如 LCS 问题里dp[0][j]和dp[i][0]都表示一个空串和某个串的公共子序列长度必然为 0。这一行一列是转移的“地基”漏了就全乱。数组越界转移里写dp[i-1]、dp[i-2]时i 从 0 开始还是从 1 开始我的习惯是让下标从 1 开始模拟多加一个 0 位置做哨兵能省掉一堆 if 判断。2.4 转移顺序迭代还是递归谁更稳转移顺序决定了“用已知值推出未知值”的流向。自顶向下的记忆化递归其实不太关心顺序——它会递归到子问题再返回自底向上的迭代则必须保证计算 dp[i] 的时候它依赖的 dp[j] 一定已经算好了。拿爬楼梯举例dp[3]依赖dp[2]和dp[1]所以按 i 从小到大遍历没问题。但有些题比如区间 DP就必须按“区间长度从小到大”遍历因为长区间的状态依赖短区间。我自己写的时候默认先写循环版本因为它没有递归栈溢出的风险调试也更直观。只有当转移关系实在没法用循环表述比如依赖顺序太奇怪时才用记忆化递归。3. 线性 DP入门必啃的经典模型3.1 爬楼梯与一维滚动从数组到 O(1) 空间爬楼梯题本身太简单但有价值的是它的学习姿势。基础版dp[i] dp[i-1] dp[i-2]需要 O(n) 空间但你发现dp[i]只依赖前两个值根本不需要保留整个数组——用两个变量滚动就行def climbStairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n 1): c a b a, b b, c return b这就是空间优化。很多 DP 题都有类似的滚动数组技巧尤其是状态转移只依赖相邻几行时。遇到二维 DP我常常只保留当前行和上一行从 O(n²) 空间压到 O(n)。省内存不说实际情况里还能大幅降低缓存 miss速度也更快。3.2 最长递增子序列 LISO(n²) 与 O(n log n) 两种写法LIS 的 O(n²) 版本是线性 DP 的必修课状态定义前面说过。完整代码如下def lengthOfLIS(nums): n len(nums) dp [1] * n # 以 nums[i] 结尾的 LIS 长度至少是 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)这个思路简单但面试里经常追问能不能优化到 O(n log n)可以但这里已经不是纯线性 DP 了而是“贪心 二分查找”。核心思想是维护一个tails数组tails[len]表示长度为len的递增子序列的最小末尾值。tails是严格递增的所以可以二分。import bisect def lengthOfLIS(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个技巧我当年也是看了好几遍才懂。你可以手动跑一遍[3, 5, 6, 2, 5, 4]遇到 3tails [3]遇到 5tails [3, 5]遇到 6tails [3, 5, 6]遇到 2替换 3tails [2, 5, 6]注意这里 2 并没有改变 LIS 的长度但它为后面的 2,4 之类的数创造了更长序列的可能性遇到 5替换第二个 5tails [2, 5, 6]遇到 4替换 5tails [2, 4, 6]最终返回 3tails数组本身不一定是真实存在的子序列但它的长度就是最长递增子序列的长度。这个点面试时说出来面试官基本会点头。3.3 最长公共子序列 LCS一张二维表的入门课LCS 问题在面试里出现频率极高经典题是“给定两个字符串 text1 和 text2返回它们的最长公共子序列长度”。状态定义是dp[i][j]表示text1[:i]和text2[:j]的最长公共子序列长度。转移方程分两种情况text1[i-1] text2[j-1]dp[i][j] dp[i-1][j-1] 1不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])这里要特别注意为什么不相等的取这个 max因为text1[:i]和text2[:j]的 LCS要么不考虑text1的第 i 个字符要么不考虑text2的第 j 个字符两种可能都试一遍。最后答案在dp[m][n]。def longestCommonSubsequence(text1, text2): m, n len(text1), len(text2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]如果你想输出具体的公共子序列就需要额外记录转移方向从 dp[m][n] 往回回溯。这个考点面试里也经常问建议你练一遍。3.4 编辑距离二维 DP 里面的“硬核代表”编辑距离LeetCode 72的思路和 LCS 很像但加了一个 cost 概念。定义dp[i][j]为把word1[:i]变成word2[:j]的最少操作数操作分三种插入、删除、替换各花费 1。转移方程如果word1[i-1] word2[j-1]dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])三个选项分别对应删除 word1 的字符、在 word1 里插入 word2 的字符、替换 word1 的字符。初始化时dp[i][0] i把 word1 前 i 个字符全删掉dp[0][j] j往空串里插入 j 个字符。这道题建议你亲手把 dp 表画出来画一次你就彻底明白二维 DP 的行列依赖关系了以后遇到各种“字符串编辑”题型都不慌。3.5 背包类 DP从 01 背包到完全背包的一句话总结背包问题是一个庞大的家族也是面试和竞赛的常客。01 背包的定义是有n个物品每个物品有重量w[i]和价值v[i]背包容量为W求能装的最大总价值。状态定义dp[i][j]表示前i个物品在容量不超过j的情况下能获得的最大价值。转移dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])空间优化后可以压成一维数组但遍历容量时必须从大到小否则物品会被重复选取。这是很多新手踩的大坑——把 01 背包和完全背包的遍历顺序搞反。完全背包里物品可以无限取所以容量从小到大遍历。我简单列个对比表类型状态转移一维容量遍历方向应用场景01 背包dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])从大到小每个物品只能选一次完全背包dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])从小到大每个物品可无限选多重背包拆成多个 01 背包二进制优化从大到小每个物品有数量上限记住一句话只要是二维转一维就想想“这个物品还能不能用第二次”能用就正着遍历不能用就倒着遍历。这句话是我带过的实习生翻车最多的地方。4. 从会做到会用拿真实题目练手的完整流程4.1 以“零钱兑换”为例走一遍完整建模题给你一个整数数组coins每种硬币数量无限求凑成金额amount所需的最少硬币数如果不可能凑成返回 -1。我拿到这道题不会直接写代码而是按这套流程走Step 1抽象状态。目标是金额 amount每个金额都可以是一个状态。定义dp[i]表示凑成金额 i 所需的最少硬币数。Step 2推导转移。凑 i 块钱最后一步一定是放了一枚面值为 c 的硬币那之前用了多少硬币是dp[i-c]。所以dp[i] min(dp[i-c] 1) for c in coins if i cStep 3初始化。dp[0] 0其他dp[i]初始化为一个大数比如amount 1用来标记“还没找到可行方案”。Step 4确认遍历顺序。amount从小到大。因为计算dp[i]需要dp[i-c]而i-c i所以正序遍历正确。代码如下def coinChange(coins, amount): dp [amount 1] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if i c: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! amount 1 else -1复杂度分析外层 O(amount)内层 O(len(coins))所以总时间 O(amount * k)空间 O(amount)。这个题有个很常见的误入歧途用贪心先拿大面额硬币去试。你会在coins [1, 3, 4]、amount 6时踩坑——贪心先拿 4就得再拿两个 1总共 3 枚但正确答案是 3 3只要 2 枚。这就是“每一步最优不等于全局最优”的经典反例也是 DP 和贪心的分水岭。4.2 蓝桥杯和 LeetCode 高频题型总结我刷题这几年发现动态规划线性dp是最常被考的入门大类蓝桥杯和 LeetCode 题库里尤其明显。按出现频率排个序一维线性 DP爬楼梯、打家劫舍、最大子数组和、买卖股票的最佳时机系列。二维线性 DP不同路径、LCS、编辑距离。背包类 DP零钱兑换、分割等和子集、最后一块石头的重量这个其实是 0/1 背包变种。区间 DP最长回文子序列、合并石头的最低成本。状态压缩 DP旅行商问题的小规模版本、上课排课问题。蓝桥杯的出题风格会更生活化。比如“砝码称重”“数字三角形”“摆花”这类题本质上换了个壳数字三角形就是每个位置从左上或右上累加求最大路径和。这种题转一下状态定义就能套模板。4.3 动态规划和搜索、剪枝、堆优化的组合用法不是所有题都单纯考 DP。我见过不少题目需要把 DP 和搜索、剪枝算法结合起来。比如 A* 算法本质上是“启发式搜索 优先队列”但它的最优性证明依赖 DP 的贝尔曼最优性原理。如果你先理解了 DP 的状态价值函数再看 A* 的f g h就非常顺畅——g 是从起点到当前点的真实代价h 是到终点的估计代价这不就是状态转移 启发式剪枝的结合吗。再比如“最长递增子序列”的 O(n log n) 解法其实是用“贪心 二分查找”代替了 DP 内层的线性扫描。这说明DP 不是终点DP 是基准解在 DP 的基础上再用其他算法优化才见水平。我实际写代码时遇到状态转移需要用单调队列、线段树、树状数组去加速的场景也不少。这类题的核心难点已经不是“怎么定义状态”而是“怎么快速求出状态转移需要的极值”。所以我建议你先把纯 DP 写熟再去学单调队列优化、斜率优化这些进阶技巧。5. 常见问题与排错速查表5.1 状态定义错了怎么办状态定义是 DP 的知识点里最玄学的。你自己定义了一个总觉得没问题的状态跑一跑发现答案错得离谱。我的排查方法是造小例子手动画表如果小例子都推不顺多半是状态定义本身不完备。举个例子LIS 问题里如果定义dp[i]为“前 i 个数的最长递增子序列长度”你会发现状态转移根本没法写因为不知道最后一个数是谁没法判断递增。所以逼自己把“结尾元素”这个额外信息塞进状态。当转移方程写不出来时第一步不是去凑方程而是去改状态定义把缺失的信息补进去。5.2 转移方程写对了但答案不对这种情况我见得特别多。要么是初始化错了前面已经反复强调求最小值和求最大值的初始化方向相反要么是遍历顺序写反了。我给自己定的几个硬性检查点手推一遍 dp 表前三个值看是否符合直觉。检查是否有dp数组越界尤其是二维 DP 的行列下标。检查有没有把比较符号写反比如求最小值时用了max。检查dp[i]转移时依赖的状态是不是“已经计算完毕”。5.3 内存超限和时间超限排查内存超限MLE先考虑滚动数组优化。如果是二维 DP试着只保留两行如果一维 DP 只依赖相邻两个值直接用变量滚动。时间超限TLE先看是不是用了 O(n²) 的普通转移而题目数据范围不允许。此时想到两件事一是优化状态数比如二维转一维二是优化单次转移比如用单调队列或二分查找把一次转移从 O(n) 降到 O(log n)。拿 LIS 举例n 10^4 时 O(n²) 勉强能过n 10^5 时就必须用 O(n log n) 的贪心 二分。我每次写完 DP都会顺手算一下最坏复杂度能不能在 1 秒内跑完一般 10^8 次操作是一个心理安全线。5.4 常见问题速查表症状可能原因解决办法答案偏小求最小值的 dp 初始化为 0初始化为大数inf或amount1答案偏大求最大值的 dp 初始化为很小的数初始化为负无穷01 背包答案重复选物品一维数组容量正序遍历容量改为从大到小遍历二维 DP 越界数组开小或下标从 0 开始忘了偏移多开一行一列用i-1访问元素时注意对应关系计算顺序错误依赖的长区间状态没先算区间 DP 改为按长度从小到大遍历死循环递归版收集 memo 没保存检查递归函数是否在每次 return 前把结果写进 memo6. 动态规划的延展与面试实操心得6.1 从线性 DP 到区间、树形、状态压缩 DP 的一条路线图动态规划家族远不止线性 DP。我给自己规划的进阶路线是这样的区间 DP先枚举区间长度再枚举区间起点转移时把区间切成两段。典型题“最长回文子序列”dp[i][j]表示s[i:j]的最长回文子序列长度状态转移里关注s[i]和s[j]是否相等。树形 DP在树上做 DP比如树的直径、树上的最大独立集。这类题的转移是递归的儿子节点的 dp 值先算好父亲再用它们转移。状态压缩 DP当输入规模极小一般 n 20时可以用一个二进制整数表示状态集合。比如旅行商问题的dp[mask][i]表示已访问的城市集合 mask最后位于城市 i 的最小路径花费。概率 DP / 期望 DP常用于游戏和随机过程题目方程里会出现E[X] 1 sum(p_i * E[Y_i])这种结构。我建议你每学一个新类型的 DP就把它的“状态定义”和“枚举顺序”单独记在笔记本里因为这两点决定了你以后遇到类似题能不能快速套用。6.2 面试与竞赛中的实用策略面试里手搓 DP我给几点实战经验先和面试官讲清楚状态定义和转移方程再写代码。一旦说错了面试官通常会给提示这时候改成本最低。写代码前先问自己这个 dp 数组是要多大是不是可以用滚动数组尽早说明自己做了空间优化一般是个加分项。面试官问“你还有什么优化吗”的时候别只会说“加缓存”。想想单调栈、二分、四毛子算法分块预处理这些进阶手段哪怕只说出思路也比沉默强。一定要自己讲测试用例。写完代码手动跑一个小例子边跑边解释这会让面试官立刻觉得你可靠。竞赛场景下蓝桥杯/ACM我自己的策略是“先暴力验证再 DP 优化”。有时候题目数据很小暴力枚举也能过但为了练 DP我会先暴力跑出正确答案再用 DP 去对拍。这也是我平时调试 DP 的绝招对拍法。随机生成小数据暴力结果和 DP 结果逐一对比哪里不一致哪里就是 bug。6.3 一些个人经验和扩展联想我看到很多人学 DP喜欢死背模板。其实换个视角会通透很多DP 的状态转移方程和强化学习里的贝尔曼方程本质上是同一种东西——都是在算“当前状态的价值等于当前奖励加上未来最优价值”。我接触深度学习算法之后回看 DP发现很多看起来高深的概念其实就是“用一张表把搜索树剪掉”。还有控制领域常见的 PID 算法、MPPT 算法本质上也在做“根据当前误差/功率状态决定下一步动作”的策略搜索。虽然它们不叫 DP但思路里都有“状态-动作-更新”的影子。学算法最有趣的地方就在这里你在 DP 里练熟的建模能力换一个领域照样能迁移。最后再分享一个我自己的小习惯每题做完强迫自己写一个注释解释 dp 数组每个维度的含义以及转移方程的物理意义。这样过一个月回看代码能秒懂当时思路下次面试复习时也不用重新推一遍。这个习惯帮我至少省下上百小时的复习时间。动态规划的学习曲线确实陡但只要你咬着牙把爬楼梯、LIS、LCS、背包、编辑距离这五个模型吃透后面再遇到任何“状态 转移”的题型你会发现都长得差不多。剩下的事情无非是两万道题换来的手感。