动态规划这个名字十个人里有九个第一次听都觉得高深莫测好像必须得是算法竞赛选手才能碰的东西。但你要是真正上手写过几道题再回过头看会发现它本质上就一句话把大问题拆成小问题并且记住小问题的答案避免重复计算。这篇东西我不会上来就甩一堆术语而是从为什么要用动态规划讲起用五道经典例题做横向对比每一道都给出完整可运行的 Python 源码再聊聊那些题解里很少写清楚、但你在实际写代码时一定会踩到的坑。无论你是刚接触算法的学生还是工作中需要自己写点策略优化代码的工程师只要跟着走一遍动态规划就没那么玄乎了。1. 动态规划到底在解决什么问题先搞清楚它的适用边界很多人学动态规划学得痛苦不是因为它本身难而是因为根本没弄明白什么题该用动态规划就硬往上套结果套得四不像。1.1 从阶乘问题说起什么是递推关系先看一个小学就接触过的例子——阶乘。5! 5 × 4 × 3 × 2 × 1但你也可以写成5! 5 × 4!。这里就出现了一个非常关键的关系要算出 n 的阶乘只需要先算出 (n-1) 的阶乘。这种我这个问题的答案依赖一个规模更小的同类问题的答案的关系就叫递推关系。def factorial(n): if n 1: return 1 return n * factorial(n - 1)这段代码没有任何动态规划的影子但它包含了动态规划最核心的种子大问题的答案可以通过小问题的答案推导出来。1.2 动态规划的三个硬性条件不是所有能递推的问题都能用动态规划。要真正用动态规划必须同时满足三个条件少了任何一个都不行最优子结构大问题的最优解包含小问题的最优解。比如你要求从北京到上海的最短路径而且这条路经过南京那么北京到南京这一段也必须是北京到南京的所有路径中最短的那条。如果不满足这个性质动态规划就没法用。重叠子问题大问题拆分出来的小问题会被反复多次计算。还是拿最短路径举例从北京到上海不管走哪条路线可能都会经过同一个中间城市那么这个中间城市的最短路径就被重复计算了。动态规划的核心价值就是把这些重复计算的结果存起来下次直接用。状态转移方程能用一个数学表达式描述大问题和小问题之间的关系。这是整个动态规划的灵魂后面每一道例题我都会重点拆这个方程是怎么来的。生活化的类比就是记账。你有记账的习惯这个月每一笔开销都记下来月底想算总支出直接把账本翻一遍加起来就行——账本就是你已经算好的子问题结果不需要重新回忆每一笔钱花在哪。1.3 什么时候不该用动态规划这一点很多人忽略但我必须说清楚否则你做题的时候容易走火入魔。遇到以下特征的题目别硬套动态规划无重叠子问题比如快速排序、二分查找每次拆出来的子问题都是独立的彼此之间没有重复。这类问题用分治更合适。需要输出具体路径动态规划擅长求最优值是多少但如果题目要你输出具体走了哪条路线虽然也能做但通常要在动态规划之外额外维护路径信息实现成本高不少。状态空间爆炸有些题目理论上可以用动态规划但状态数量有几十个维度空间复杂度高到无法承受。比如有些涉及一堆物品、多种限制条件的组合优化题这时候往往得另寻出路。我看过太多人拿到一个题不管三七二十一先写动态规划写不出来就说这题太难了。其实大概率是压根没用对方法。2. 一套能复用的思考框架从暴力递归到动态规划动态规划不是凭空想出来的它有一条非常清晰的演进路径暴力递归 → 记忆化搜索 → 动态规划。我强烈建议你遇到新题的时候先按照这个顺序走一遍而不是一上来就盯着状态转移方程憋半天。2.1 第一步先写暴力递归暴力递归的关键是不要想优化就按最直白的方式把问题描述成递归。以经典的斐波那契数列为例题目要求f(n) f(n-1) f(n-2)其中f(0)0, f(1)1。最朴素的写法就是def fib_brute(n): if n 1: return n return fib_brute(n - 1) fib_brute(n - 2)这段代码逻辑完全正确但跑n50的时候就会卡到怀疑人生。问题出在哪儿你可以画一下递归调用树算fib(5)需要算fib(4)和fib(3)算fib(4)又需要算fib(3)和fib(2)。注意看fib(3)被重复计算了至少两次。当 n 变大这种重复会呈现指数级爆炸时间复杂度是 O(2^n)不是吓唬你是真的慢到 n50 就基本跑不完了。2.2 第二步加一层记忆变成记忆化搜索既然问题是重复计算那就把已经算过的结果存起来。用一个字典或者数组当缓存每次计算前先查一下查到了直接返回算不到就存进去def fib_memo(n, memoNone): if memo is None: memo {} if n 1: return n if n in memo: return memo[n] memo[n] fib_memo(n - 1, memo) fib_memo(n - 2, memo) return memo[n]这个版本的时间复杂度瞬间从 O(2^n) 降到了 O(n)n100 也毫无压力。这其实已经抓住动态规划的本质了——用空间换时间。这种从上往下递归 记忆化缓存的写法就是记忆化搜索。2.3 第三步翻转计算方向得到标准动态规划记忆化搜索虽然能解决问题但递归本身有函数调用开销而且当递归深度特别大时还有爆栈风险。更好的做法是自底向上先算f(0)、f(1)再算f(2)一步步滚到f(n)。def fib_dp(n): if n 1: return n dp [0] * (n 1) dp[0], dp[1] 0, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这才是我们常说的动态规划形态。整个过程非常像你在Excel里做公式下拉每一项都只依赖前面已经算好的行算完后面就再也不回头看了。至于网上各种优化版本的只用两个变量滚动更新都只是在这个基础上的空间优化先把标准版本写对再说。这套暴力递归 → 记忆化搜索 → 动态规划的三步走我后面讲的五道例题思路全部来自这里。3. 五道典型例题逐题拆解状态定义、转移方程、源码对照说再多理论不落到具体题目上都是空的。下面这五道题从易到难排序每道题都是面试和工程里的常客。我先讲怎么想再给完整代码最后说坑在哪。3.1 爬楼梯一模一样又能复习一遍题目你正在爬楼梯每次只能爬 1 阶或 2 阶问爬到第 n 阶有多少种不同的方法。这道题和斐波那契几乎一模一样。状态定义dp[i]表示爬到第 i 阶的方法总数。转移方程到达第 i 阶要么是从第 i-1 阶迈 1 步上来的要么是从第 i-2 阶迈 2 步上来的所以dp[i] dp[i-1] dp[i-2]。边界条件dp[0]1原地不动算一种dp[1]1。def climb_stairs(n): if n 1: return 1 dp [0] * (n 1) dp[0], dp[1] 1, 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]是不是觉得这不就是斐波那契换了个皮没错。很多动态规划题都是同一个内核换了不同的题目背景。你如果能把这道题直接优化成只维护两个变量说明对空间优化已经有感觉了def climb_stairs_optimized(n): if n 1: return 1 prev, cur 1, 1 for _ in range(2, n 1): prev, cur cur, prev cur return cur3.2 01背包动态规划的扛把子必须吃透题目有 N 件物品和一个容量为 W 的背包。每件物品有自己的重量w[i]和价值v[i]问怎么装能让背包里的总价值最大。01背包是动态规划里最经典的题型没有之一。它衍生出的变体题型多到数不清所以这道题的思路值得花大力气搞清楚。状态定义dp[i][j]表示考虑前 i 件物品背包容量为 j 时能获得的最大总价值。转移方程是这道题的核心需要仔细理解。对于第 i 件物品只有两种选择不选它那价值就是dp[i-1][j]和前 i-1 件物品、容量 j 的情况完全一样。选它那前提是当前容量j w[i]装进去之后背包剩余容量是j - w[i]但你获得了价值v[i]。于是总价值是dp[i-1][j-w[i]] v[i]。所以状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 当 j w[i] dp[i][j] dp[i-1][j] 当 j w[i]写成代码def knapsack_01(weights, values, capacity): n len(weights) # dp[i][j] 表示前 i 件物品装入容量 j 的背包的最大价值 # 多开一行一列方便处理 i0 或 j0 的边界 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 1): if weights[i - 1] j: dp[i][j] max( dp[i - 1][j], # 不选第 i 件 dp[i - 1][j - weights[i - 1]] values[i - 1] # 选第 i 件 ) else: dp[i][j] dp[i - 1][j] # 装不下只能不选 return dp[n][capacity]跑个测试看看weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 5 # 最优选择第1件(价值3) 第2件(价值4) 重量235总价值7 print(knapsack_01(weights, values, capacity)) # 输出 7我能给你的最大建议是这道题别只背代码一定要自己动手把二维 dp 表一行一行填一遍。填表的过程你会真正理解选与不选两个分支分别对应什么后面的一维滚动数组优化才看得懂。3.3 零钱兑换min版本的背包问题题目给定不同面额的硬币coins和一个总金额amount求凑成总金额所需的最少的硬币个数。每种硬币数量无限。这道题和01背包对比着看非常有意思。01背包是每件物品最多选一次零钱兑换是每种硬币可以无限选。但它们的核心框架完全一致。状态定义dp[i]表示凑出金额 i 所需的最少硬币数。转移方程凑出金额 i最后一步一定是用了一枚硬币c那么凑出i-c再加上这一枚硬币就是dp[i-c] 1。我们要在所有可能的硬币面额里挑出最小值dp[i] min(dp[i - c] for c in coins if c i) 1边界条件dp[0] 0。其他金额初始化为一个很大的数比如float(inf)表示还没凑出来。def coin_change(coins, amount): # dp[i] 表示凑出金额 i 需要的最少硬币数 dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for c in coins: if c i: dp[i] min(dp[i], dp[i - c] 1) return dp[amount] if dp[amount] ! float(inf) else -1踩坑提示很多新手会先把dp数组初始化为-1然后判断的时候晕头转向。float(inf)在这类求最小值的题目里是最好用的初始值因为它天然参与min比较却不会被选中最后再统一判断一次是否不可达就好。coins [1, 2, 5] amount 11 print(coin_change(coins, amount)) # 输出 3 (551)3.4 最长公共子序列二维状态找到对不上的情况怎么办题目给定两个字符串text1和text2返回它们的最长公共子序列的长度。子序列不要求连续但必须保持相对顺序。这道题是两个序列类动态规划的鼻祖很多字符串匹配问题都是从它衍生出去的。状态定义dp[i][j]表示text1的前 i 个字符和text2的前 j 个字符的最长公共子序列长度。转移方程要分情况讨论如果text1[i-1] text2[j-1]那这两个字符一定可以拼到公共子序列的末尾所以dp[i][j] dp[i-1][j-1] 1。如果两个字符不相等那当前这个位置至少能继承哪边的结果可能是text1的前 i-1 个字符和text2的前 j 个字符的结果也可能是text1的前 i 个字符和text2的前 j-1 个字符的结果取更大的那个dp[i][j] max(dp[i-1][j], dp[i][j-1]) 当 text1[i-1] ! text2[j-1]def longest_common_subsequence(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] print(longest_common_subsequence(abcde, ace)) # 输出 3这里有一个特别容易让人困惑的点为什么text1[i-1]和text2[j-1]不等时要取max(dp[i-1][j], dp[i][j-1])而不是dp[i-1][j-1]因为只退一个序列和两个序列各退一格相比前者保留了更多的可能性。dp[i-1][j]包含了所有在前 i-1 个字符里能匹配 j 个字符的情况而dp[i-1][j-1]只是其中一部分所以从覆盖范围来看max(dp[i-1][j], dp[i][j-1])一定不小于单纯的dp[i-1][j-1]直接用这个表达式就没有遗漏。3.5 最长递增子序列变体多到数不完的一道题题目给定一个无序整数数组找到其中最长严格递增子序列的长度。这道题和最长公共子序列名字很像但状态定义和转移完全不一样单独拿出来对比学习会特别涨功力。状态定义dp[i]表示以第 i 个元素结尾的最长递增子序列的长度。注意不是前 i 个元素而是必须包含第 i 个元素。转移方程对每一个i往前面找所有比nums[i]小的nums[j]那么nums[i]可以拼在nums[j]后面形成dp[j] 1的新子序列。取所有可能的最大值dp[i] max(dp[j] 1 for j in range(i) if nums[j] nums[i])初始值为 1def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n 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) print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])) # 输出 4例如 2,3,7,101注意一个很容易犯的错最后返回的是max(dp)而不是dp[n-1]。因为最长递增子序列不一定以最后一个元素结尾可能在数组中间就已经达到最长了。很多人第一次写这道题返回dp[-1]导致答案差了半天排查不出来。4. 五道题横向对比状态定义和转移方程放在一起看规律就藏不住把上面的五道题放在同一张表里动态规划的套路会变得非常清晰题目状态定义转移方程时间复杂度空间复杂度爬楼梯dp[i]到第 i 阶的方法数dp[i] dp[i-1] dp[i-2]O(n)O(1) 可优化01背包dp[i][j]前 i 件物品装进容量 j 的最大价值dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]]v[i])O(N×W)O(W) 可优化零钱兑换dp[i]凑出金额 i 的最少硬币数dp[i] min(dp[i-c]1 for c in coins)O(amount×硬币种类)O(amount)最长公共子序列dp[i][j]两个前缀的最长公共子序列长度相等走1不等走max继承O(m×n)O(m×n)最长递增子序列dp[i]以 i 结尾的最长递增子序列长度dp[i] max(dp[j]1) for ji if nums[j]nums[i]O(n²)O(n)只看这张表能得出什么结论第一状态定义是最关键的一步。状态定错了后面的转移方程怎么推都是歪的。一维还是二维以谁结尾还是前几个代表最大值还是最小值这些决定会直接影响整个题目的难度。我个人的经验是先把所有的约束条件、题目问的东西列出来再考虑用几个变量能把这些条件全覆盖。比如背包问题显然需要物品编号和容量两个维度所以状态必然是二维的。第二转移方程就是最后一步怎么走。倒着想如果我已经知道所有子问题的答案了那么从最后一步往前推最终答案是怎么合成的爬楼梯的最后一步是迈1阶或迈2阶背包的最后一步是最后一件物品选还是不选零钱兑换的最后一步是最后用哪枚硬币。想清楚最后一步转移方程就写出来了一大半。第三空间复杂度的优化空间往往比时间复杂度的优化空间大得多。01背包、爬楼梯、零钱兑换都能优化成一维数组最长公共子序列可以优化成滚动数组最大递增子序列还有二分的优化版本时间复杂度 O(n log n)。但优化的前提是二维的暴力写法你已经完全理解了否则一维数组的倒序遍历覆盖顺序解释起来特别费劲自己写更容易整错。5. 两个非常容易搞混的对比完全背包和 LIS 的进阶坑如果你上面五道题都吃透了那再往下走有两个进阶方向我认为特别值得单独说明它们也是面试官喜欢往下追问的点。5.1 01背包 vs 完全背包循环顺序决定逻辑零钱兑换实际上是完全背包的一种形式——每种物品无限取。把零钱兑换和01背包放在一起看它们的转移方程很像唯一的区别在于01背包每件物品只能拿一次完全背包每件物品可以拿无限次。这个区别表现在代码里就是遍历的顺序# 01背包外层循环物品内层循环容量容量必须倒序 def knapsack_01_1d(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity] # 完全背包容量正序 def knapsack_complete_1d(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(weights[i], capacity 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]为什么01背包要倒序、完全背包要正序这是一个教科书上写了但你未必真正理解的细节。一维数组dp[j]在更新时会覆盖掉之前的旧值。01背包里我们要求dp[j - weights[i]]必须是**上一轮物品前 i-1 件**计算出来的值也就是还没被当前物品更新过的历史值。如果正序循环j从小到大等处理到j时较小的j - weights[i]可能已经在本轮被更新过了这就相当于同一件物品被拿了多次恰好变成完全背包的行为。倒序循环从大到小j - weights[i]一定比j小而它在本轮循环里还没被访问到所以读到的还是上一轮的值保证了每件物品只拿一次。顺着这个逻辑你就明白完全背包为什么正序了——我们就是想让同一件物品可以被反复拿正序更新时dp[j - weights[i]]已经被本轮刷新过包含了当前这件物品已经拿过若干次的情况自然就实现了无限取用。5.2 LIS 的O(n log n)优化不只是为了复杂度前面写的 LIS 版本是 O(n²)数据量一上万就明显吃力。这里分享一个基于贪心 二分的优化方法也是大厂面试喜欢追着问的。核心思想维护一个数组tailstails[k]表示长度为 k1 的递增子序列中结尾元素的最小值。然后遍历数组对每个元素在tails里找到第一个大于等于它的位置替换掉。如果找不到比它大的说明它能接在现有最长子序列后面直接 append。import bisect def length_of_lis_binary(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)拿[10, 9, 2, 5, 3, 7, 101, 18]走一遍10 → tails: [10]9 → 替换10 → tails: [9]2 → 替换9 → tails: [2]5 → 比2大append → tails: [2, 5]3 → 替换5 → tails: [2, 3]7 → append → tails: [2, 3, 7]101 → append → tails: [2, 3, 7, 101]18 → 替换101 → tails: [2, 3, 7, 18]最终长度4。注意tails里存的并不是真正的子序列而是每个长度的最小结尾但它能保证len(tails)等于最长递增子序列的长度。这个思路我第一次看的时候也转不过弯后来想明白了一个关键点就通了以更小的数字结尾永远比以更大的数字结尾更有潜力——更小意味着后面能接更多更大的数所以用一个最小值来代表某个长度是划算的。5.3 五道题之外的举一反三如果你已经能独立推导出上面几道题的转移方程那么下面这些变体题你就可以尝试自己去做思路全部来自上面打家劫舍一维DP和爬楼梯类似但变成了求最大值最大子数组和状态定义是以 i 结尾和 LIS 很像转移方程更简单编辑距离二维DP和最长公共子序列共享框架分割等和子集本质是01背包的能凑出某个和的判定问题不同的二叉搜索树有点难但状态定义和转移方程依然能顺着推6. 源码能跑通只是第一步这些隐性问题你一定也会遇到代码写出来能跑通对动态规划来说只算完成了一半。真正考验人的是你跑一些特殊数据或者重新优化时冒出来的问题。这些坑我基本都踩过列出来帮你省点时间。6.1 初始化到底该是0还是infinity这是个特别常见的问题。原则很简单求最大值初始化为0求最小值初始化为无穷大。但如果题目有额外的条件比如要求结果必须能由子问题拼出来像零钱兑换初始化为float(inf)后就一定别忘了在最后判断不可达的情况。还有一个小细节是 dp 数组长度该开n还是n1。我建议只要状态定义里包含前 i 个前 j 个这种下标语义一律开n1把下标0留出来做边界代码写起来会顺手非常多也能避免很多越界问题。6.2 下标偏移是字符串类DP最大的坑拿最长公共子序列来说dp[i][j]对应的是text1[i-1]和text2[j-1]不是text1[i]和text2[j]。因为dp[i][j]表示的是前 i 个字符和前 j 个字符字符下标从0开始所以第 i 个字符实际是text1[i-1]。这个偏移关系没搞清写循环的时候一定迷迷糊糊调试起来还特别费劲。我的经验是先在代码注释里把状态定义完整写出来再动手写循环。比如# dp[i][j]: text1 的前 i 个字符和 text2 的前 j 个字符的 LCS 长度 # 所以当 text1[i-1] text2[j-1] 时说明新的一对字符相等这样写着写着就不会晕了。6.3 不要把 dp 的值和题目给的元素值搞混这是新手经常出现的认知混乱。dp[i]存的是答案的值方法数、长度、最大收益不是原数组nums[i]的值。比如 LIS 里dp[i]表示以第 i 个元素结尾的最长子序列长度它跟nums[i]没有直接数值关系比较大小的对象是nums[j]和nums[i]做加法的对象才是dp[j] 1。我见过有人写出if dp[j] dp[i]这种比较一看就是把题意理解歪了。6.4 空间优化的时候注意维度压缩的方向01背包压缩成一维数组的时候要倒序遍历容量这是最常见的优化形式。但如果你优化的是一个二维的DP表比如最长公共子序列通常是用滚动数组只保留上一行和当前行。这里有个容易出错的地方滚动数组的当前行在更新时会覆盖上一行的旧值所以dp[i-1][j-1]这种值要先保存下来再用。def longest_common_subsequence_roll(text1, text2): m, n len(text1), len(text2) prev [0] * (n 1) curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: curr[j] prev[j - 1] 1 else: curr[j] max(prev[j], curr[j - 1]) prev, curr curr, prev return prev[n]注意curr[j] max(prev[j], curr[j - 1])里的curr[j-1]它必须是本行已经算出来的那个值而不是上一行的prev[j-1]这是滚动数组写法里最隐蔽的坑之一。写完之后建议拿几个测试用例手工对比二维版本的输出确认一致再放心。6.5 肉眼填表法调试动态规划的王牌技巧最后分享一个我用了很多年的笨但极其有效的方法——打印 dp 表。不论哪道题跑完循环后把整个 dp 二维数组打印出来一行一行对照着看你的逻辑漏洞一定会自己跳出来。尤其是01背包这种明明感觉转移方程没写错输出值却差一点填一遍表马上就知道是初始化错了还是循环边界错了。# 以01背包为例打印整个 dp 表 def knapsack_with_debug(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 1): if weights[i - 1] j: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]) else: dp[i][j] dp[i - 1][j] print(f第{i}件物品处理后: {dp[i]}) return dp[n][capacity]我现在遇到复杂的新题第一版永远是二维dp 打印表跑通了才开始考虑空间优化。想一步到位直接写一维优化版本出了问题反而更浪费时间。动态规划这个东西说破天也就是状态、转移、边界六个字但真正让它变得难以上手的是怎么从题目描述里看出这三样东西的翻译过程。我自己的体会是没有捷径只有靠足够的题目量喂出来。不需要一天刷二十道但每道题都按暴力递归 → 记忆化搜索 → 动态规划的思路过一遍画一次递归树填一次dp表比囫囵吞枣刷一页题要管用得多。等你熟练到能把这一类题的题型归纳成几张大表再拿到新题的时候就会有种哦这个换了个皮而已的轻松感了。