1. 为什么我要从零写一套动态规划拆解动态规划这四个字几乎是每个学算法的人绕不过去的一道坎。我见过太多人在面试前突击背几道背包问题、最长公共子序列的模板结果题目稍微换个皮就完全没思路。也见过有人刷了两百道DP题遇到新题还是只能干瞪眼。问题出在哪不是题刷得不够多而是从一开始就没有建立起对动态规划这门“手艺”的正确认知。我自己当年学DP也走过弯路。最早接触的是斐波那契数列的递推写法觉得不过如此后来碰到零钱兑换、编辑距离开始觉得有点意思再往后遇到状态压缩、区间DP、树形DP整个人就懵了。真正让我开窍的不是又刷了多少题而是有一天我突然想明白了一件事动态规划本质上不是一种算法而是一种思考问题的方式——它教你怎么把一个大麻烦拆成一串小麻烦然后从小麻烦的答案里拼出大麻烦的答案。这套拆解我打算分几篇来写这是第一篇重点解决三个问题动态规划到底在干什么、怎么判断一道题能不能用DP、以及最核心的——状态和转移方程到底怎么设计。我不会一上来就甩一堆数学公式而是用最直白的话和大量例子把每个概念揉碎了讲。适合谁看如果你正在学算法、准备面试、或者单纯想搞明白这个被说烂了却总也学不透的东西那这篇内容就是写给你的。哪怕你之前完全没接触过DP只要会写最基本的循环和递归就能跟上。2. 动态规划到底在解决什么问题2.1 从一个最朴素的例子说起假设你要爬一个n级的楼梯每次只能走1级或者2级问一共有多少种走法。这个问题太经典了经典到很多人一看到就知道答案是斐波那契数列。但我想让你关注的是思考过程而不是答案本身。当你站在第n级台阶上往回看你最后一步是怎么上来的要么是从第n-1级走1级上来的要么是从第n-2级走2级上来的。没有第三种可能。所以走到第n级的走法总数就等于走到第n-1级的走法数加上走到第n-2级的走法数。写成式子就是f(n) f(n-1) f(n-2)。这个式子就是所谓的“状态转移方程”。而f(n)就是“状态”它表示走到第n级台阶的走法总数。你看动态规划的核心思想在这里已经体现得淋漓尽致了当前问题的答案可以由若干个更小规模的同类问题的答案推导出来。那为什么不能直接用递归算因为递归会把同一个子问题重复计算无数次。算f(5)需要f(4)和f(3)算f(4)又需要f(3)和f(2)f(3)被算了两次。n稍微大一点计算量就爆炸了。动态规划的解决办法就是把每个子问题的答案记下来用的时候直接查表不重复算。这就是“记忆化”或者“填表”的思想。2.2 动态规划与分治、贪心的本质区别很多人分不清动态规划、分治法、贪心算法。它们确实有相似之处都是把大问题拆成小问题但拆的方式和合并的方式完全不同。分治法是把问题拆成若干个互不重叠的子问题分别求解后再合并。比如归并排序左半边和右半边完全独立排好之后一合并就完事。子问题之间没有交集所以不需要记录中间结果。贪心算法是每一步都选当前看起来最优的期望最终得到全局最优。它不管子问题之间有没有重叠也不回头检查之前的选择。贪心能用的前提是问题具有“贪心选择性质”这个条件其实很苛刻大部分问题不满足。动态规划则专门对付子问题重叠的情况。它承认子问题会被反复用到所以老老实实把每个子问题的解存起来。同时它也不像贪心那样只顾眼前而是通过状态转移方程把所有的可能性都考虑进去最终选出最优的那个。你可以这么理解分治是各干各的然后拼起来贪心是一条路走到黑动态规划是做好笔记、步步为营。2.3 最优子结构与重叠子问题动态规划能用的前提是两个性质最优子结构和重叠子问题。最优子结构的意思是大问题的最优解一定包含了子问题的最优解。拿最短路径来说如果从A到C的最短路径经过B那么A到B的那段一定也是最短的B到C的那段也一定是最短的。如果不是你换一条更短的整体不就更短了吗这就矛盾了。所以只要问题具有最优子结构我们就可以放心地从子问题的最优解推导大问题的最优解。重叠子问题的意思是在递归求解的过程中同一个子问题会被多次遇到。爬楼梯那个例子就是典型f(3)在算f(5)和f(4)时都被用到了。如果子问题不重叠那用分治就好了没必要上DP。这两个性质缺一不可。没有最优子结构你从子问题推不出大问题没有重叠子问题你记录中间结果也没意义白白浪费空间。注意很多人误以为“最优子结构”就是“局部最优能推出全局最优”这其实是贪心的思路。最优子结构说的是大问题的最优解里面包含了子问题的最优解但不代表你每一步都选局部最优就能得到全局最优。这个区别一定要想清楚。3. 状态设计动态规划最核心也最难的一步3.1 状态到底是什么如果把动态规划比作盖房子那状态就是砖块转移方程就是水泥。没有砖块水泥再多也砌不成墙。状态设计对了转移方程往往水到渠成状态设计错了怎么推都推不出来。那状态到底是什么简单说状态就是你对当前局面的一个完整描述。它必须包含足够的信息使得从这个状态出发你能做出下一步的决策并且能判断这个状态的好坏。同时状态又不能包含多余的信息否则状态空间会爆炸。拿爬楼梯来说状态就是“当前在第几级台阶”。这个信息足够了因为从第i级台阶出发你只需要知道i是多少就能决定下一步走到i1还是i2。至于你之前是怎么走到第i级的走了多少步用了什么姿势统统不重要。这就是状态的“无后效性”——当前状态一旦确定后续的决策只依赖于当前状态与到达这个状态的路径无关。3.2 一维状态与多维状态的取舍状态可以是多维的。爬楼梯是一维状态因为只需要一个变量就能描述局面。但很多问题一个变量不够用。比如经典的“零钱兑换”给你若干种面额的硬币问凑出金额n最少需要几枚硬币。这里状态是“当前需要凑出的金额”还是一维的。但如果加一个限制条件比如每种硬币最多只能用一次那状态就变成二维了dp[i][j]表示用前i种硬币凑出金额j的最少硬币数。因为你需要知道“现在考虑到第几种硬币了”和“还需要凑多少钱”这两个信息。再比如“最长公共子序列”两个字符串状态自然是二维的dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列长度。因为你需要同时知道两个字符串各自处理到哪了。那什么时候该加维度判断标准很简单如果你发现当前状态不足以做出下一步决策或者不足以判断当前局面的优劣那就说明缺信息需要加维度。但每加一维状态空间就乘一个量级时间和空间复杂度都会上去。所以要在“信息足够”和“空间可控”之间找平衡。3.3 状态的无后效性为什么重要无后效性是状态设计的一条铁律。它的意思是一旦当前状态确定了未来只与当前状态有关与怎么到达当前状态的历史路径无关。为什么这条这么重要因为如果未来依赖于历史路径那你的状态就必须把历史路径也编码进去状态空间会变得无比巨大动态规划就退化成暴力搜索了。举个例子。假设你在玩一个游戏角色有生命值和魔法值两个属性。如果你设计的状态是“当前生命值和魔法值”那没问题因为下一步能做什么只取决于当前的血量和蓝量。但如果你设计的状态是“当前生命值、魔法值、以及之前每一步的选择”那就完蛋了状态多到没法存。所以设计状态的时候一定要问自己我记录的信息是否足以唯一确定后续的决策如果两个不同的历史路径到达了同一个状态它们后续的最优决策是否相同如果相同说明状态设计是合理的如果不同说明状态里缺了关键信息需要补上。实操心得我刚开始学DP的时候经常犯一个错误——状态里塞了太多没用的信息。比如做背包问题非要把“当前背包里装了哪些物品”也记下来。其实完全没必要因为背包问题只关心“当前容量还剩多少”和“当前考虑到第几个物品了”具体装了哪些物品不影响后续决策。状态越精简效率越高。4. 转移方程从状态到状态的桥梁4.1 转移方程的本质是决策枚举状态设计好了接下来就是转移方程。转移方程说白了就是在当前状态下你有哪些选择每个选择会导致什么后果哪个后果最好用数学语言说转移方程就是dp[state] opt{ dp[prev_state] cost }其中opt是最优化操作取最大、最小、求和等prev_state是做出某个决策后到达的前一个状态cost是这个决策的代价。还是拿爬楼梯举例。状态dp[i]表示走到第i级的走法数。在当前状态i下你只能从i-1或i-2走过来。所以dp[i] dp[i-1] dp[i-2]。这里的“决策”就是“最后一步是走1级还是走2级”两种决策对应的前一个状态分别是i-1和i-2代价都是1种走法所以加起来。再拿零钱兑换举例。状态dp[j]表示凑出金额j所需的最少硬币数。在当前状态j下你可以选择任何一种面额的硬币coin。如果选了coin那你就从状态j-coin转移过来代价是1枚硬币。所以dp[j] min{ dp[j-coin] 1 }对所有满足coin j的硬币面额取最小值。你看转移方程的核心就是枚举所有可能的决策然后从中选出最优的。枚举的范围取决于问题本身但思路是通用的。4.2 边界条件别让程序在起点就翻车转移方程描述了状态之间怎么跳但总得有个起点。边界条件就是那些不需要转移、可以直接给出答案的状态。爬楼梯的边界是dp[0] 1站在地面不动就是一种走法和dp[1] 1走到第1级只有一种走法。零钱兑换的边界是dp[0] 0凑出金额0不需要任何硬币。最长公共子序列的边界是dp[0][j] 0和dp[i][0] 0任意字符串和空串的公共子序列长度都是0。边界条件看起来简单但实际写代码的时候特别容易出错。我见过太多人转移方程推得漂漂亮亮结果边界写错了整个答案全盘皆输。比如爬楼梯如果dp[0]设成0那dp[2] dp[1] dp[0] 1 0 1但实际应该是2走两次1级或者一次走2级。一个边界错误后面全错。注意边界条件一定要根据问题的实际语义来确定不能凭感觉。建议在草稿纸上手动算几个小规模的情况验证边界值是否正确。比如爬楼梯手动算一下n0,1,2,3的情况看看边界设成多少才能让结果对得上。4.3 从递归到递推两种实现路径有了状态和转移方程实现方式有两种递归加记忆化和递推填表。递归加记忆化的写法更贴近转移方程的数学形式代码通常更简洁也更容易理解。思路是写一个递归函数solve(state)先查表看这个状态有没有算过算过就直接返回没算过就按照转移方程递归计算算完存表再返回。这种写法也叫“自顶向下”。递推填表的写法是先确定状态的遍历顺序然后从边界条件开始一层一层往外推直到算出目标状态。这种写法也叫“自底向上”。它的好处是没有递归栈开销速度通常更快而且方便做空间优化。两种写法各有优劣。递归加记忆化写起来快不容易搞错遍历顺序但递归深度太大会爆栈。递推填表效率高但需要想清楚遍历顺序顺序错了结果就错了。我的建议是初学的时候先用递归加记忆化因为它的结构和转移方程几乎一一对应不容易出错。等熟练了再改成递推填表追求更高的效率。下面用爬楼梯举例两种写法都给你。递归加记忆化def climb(n, memo{}): if n 1: return 1 if n in memo: return memo[n] memo[n] climb(n-1, memo) climb(n-2, memo) return memo[n]递推填表def climb(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]你看递推版本里那个for循环的顺序就是从前往后因为dp[i]依赖于dp[i-1]和dp[i-2]所以必须先把小的算出来。如果依赖关系反过来遍历顺序就要反过来。这就是为什么递推填表需要想清楚遍历顺序。5. 实战拆解从题目到代码的完整流程5.1 案例一最大子数组和题目给一个整数数组找出一个连续子数组使得它的和最大返回这个最大和。第一步设计状态。最直接的想法是dp[i]表示“以第i个元素结尾的最大子数组和”。为什么强调“以第i个元素结尾”因为子数组必须是连续的如果dp[i]表示“前i个元素中的最大子数组和”那转移的时候你没法判断第i个元素要不要接在前面的子数组后面。而“以第i个元素结尾”这个定义天然保证了连续性。第二步推转移方程。对于dp[i]第i个元素有两种选择要么接在前面的子数组后面要么自己单独成为一个子数组。如果接在后面那和就是dp[i-1] nums[i]如果单独和就是nums[i]。我们要最大的所以dp[i] max(dp[i-1] nums[i], nums[i])。第三步确定边界。dp[0] nums[0]因为第一个元素结尾的子数组只有它自己。第四步确定答案。答案不是dp[n-1]而是max(dp[0], dp[1], ..., dp[n-1])因为最大子数组不一定以最后一个元素结尾。代码实现def max_subarray(nums): n len(nums) dp [0] * n dp[0] nums[0] ans dp[0] for i in range(1, n): dp[i] max(dp[i-1] nums[i], nums[i]) ans max(ans, dp[i]) return ans这个题还可以做空间优化因为dp[i]只依赖于dp[i-1]所以用一个变量滚动更新就行不需要整个数组。优化后空间复杂度从O(n)降到O(1)。def max_subarray_optimized(nums): cur nums[0] ans nums[0] for i in range(1, len(nums)): cur max(cur nums[i], nums[i]) ans max(ans, cur) return ans实操心得空间优化是动态规划进阶的必修课。很多DP问题的状态转移只依赖于前一层或前几个状态这时候就可以用滚动数组或者变量来压缩空间。但要注意空间优化之后代码的可读性会下降如果是在面试中建议先写未优化的版本确认逻辑正确后再提优化思路。5.2 案例二最长递增子序列题目给一个整数数组找出最长递增子序列的长度。子序列不要求连续但要求保持相对顺序。第一步设计状态。dp[i]表示“以第i个元素结尾的最长递增子序列长度”。同样强调“以第i个元素结尾”理由和上面一样。第二步推转移方程。对于dp[i]我们需要往前看所有j i且nums[j] nums[i]的位置。如果nums[i]能接在nums[j]后面那长度就是dp[j] 1。我们要最长的所以dp[i] max(dp[j] 1)对所有满足j i且nums[j] nums[i]的j。第三步边界。每个元素至少可以自己构成一个长度为1的递增子序列所以dp[i]初始值都是1。第四步答案。max(dp[0], ..., dp[n-1])。代码实现def length_of_lis(nums): n len(nums) dp [1] * n ans 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans这个题的时间复杂度是O(n^2)因为有两层循环。它还有一个O(n log n)的优化解法用到了贪心加二分查找但那个解法已经不太像典型的动态规划了这里先不展开。5.3 案例三零钱兑换题目给若干种硬币面额和一个目标金额问凑出目标金额最少需要几枚硬币。每种硬币可以用无限次。第一步状态。dp[j]表示凑出金额j所需的最少硬币数。第二步转移方程。对于金额j我们可以选择任何一种面额为coin的硬币。如果选了它就相当于从金额j-coin转移过来代价是1枚硬币。所以dp[j] min(dp[j-coin] 1)对所有满足coin j的硬币面额取最小。第三步边界。dp[0] 0凑出金额0不需要硬币。其他dp[j]初始化为一个很大的数比如无穷大表示暂时无法凑出。第四步答案。dp[target]如果它还是无穷大说明无法凑出返回-1。代码实现def coin_change(coins, amount): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for j in range(1, amount 1): for coin in coins: if coin j: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! INF else -1注意这里的遍历顺序外层循环遍历金额内层循环遍历硬币。为什么不能反过来因为每种硬币可以用无限次如果外层遍历硬币、内层遍历金额那对于每种硬币你只能沿着金额递增的方向更新一次无法实现“同一种硬币用多次”的效果。外层遍历金额、内层遍历硬币才能保证每种硬币在任意金额下都可以被重复选择。注意背包类问题的遍历顺序非常讲究。0-1背包要求每种物品只能用一次所以外层遍历物品、内层遍历容量且容量从大到小完全背包要求每种物品可以用无限次所以外层遍历物品、内层遍历容量且容量从小到大。如果搞反了0-1背包会变成完全背包完全背包会变成0-1背包。这个坑我踩过不止一次每次都要在草稿纸上画一遍才放心。6. 常见问题与排查技巧实录6.1 状态转移方程推不出来怎么办这是最常见的问题。很多人卡在这一步盯着题目发呆不知道怎么从子问题推到父问题。我的经验是不要硬推先手动模拟。拿一个具体的小例子在纸上一步一步算看看每一步的答案是怎么从前面几步的答案算出来的。比如爬楼梯你手动算n1,2,3,4,5把结果列出来然后观察规律。很多时候规律一出来转移方程就跟着出来了。另一个技巧是“从最后一步倒推”。问自己到达最终状态的前一步可能是什么把所有可能的前一步列出来然后看当前状态和前一步状态之间的关系。这个方法对很多问题都有效因为最终状态往往是问题最明确的地方。如果还是推不出来那可能是状态设计有问题。回头检查一下状态是否包含了足够的信息是否满足无后效性如果状态本身就不对转移方程当然推不出来。6.2 边界条件总是写错怎么办边界条件写错通常是因为没有想清楚“最小规模的问题是什么”。我的建议是在写代码之前先把n0,1,2,3的情况手动算一遍把结果写在纸上。然后写代码的时候用这些手动算的结果去验证边界条件。另外边界条件不一定是dp[0]或dp[0][0]。有些问题的边界是多个比如最长公共子序列dp[0][j]和dp[i][0]都是边界。有些问题的边界需要特殊处理比如零钱兑换中dp[0]0但其他dp[j]初始化为无穷大。所以一定要根据具体问题来确定边界不能套模板。6.3 遍历顺序搞反了怎么发现遍历顺序搞反的典型症状是代码逻辑看起来没问题但结果就是不对或者部分测试用例通过、部分不通过。发现的方法很简单在代码里加打印把每一步的状态值输出出来和手动模拟的结果对比。如果发现某个状态的值依赖于一个还没被计算的状态那就说明遍历顺序反了。比如0-1背包问题如果内层容量从小到大遍历那dp[j]会依赖于dp[j-weight]已经在本轮被更新过相当于同一个物品被用了多次。这时候你打印dp数组会发现结果比正确答案大因为物品被重复使用了。把容量改成从大到小遍历问题就解决了。6.4 空间优化后结果不对怎么排查空间优化之后结果不对通常是因为优化后的变量没有正确初始化或者更新顺序有问题。排查方法先写一个未优化的版本确认结果正确。然后逐步优化每优化一步就对比一次结果。如果优化后结果变了说明优化过程中引入了bug。常见的bug包括滚动数组的初始值没设对、变量更新顺序反了导致使用了新值而不是旧值、多维数组压缩成一维时索引搞错了。实操心得空间优化虽然能降低空间复杂度但会牺牲代码的可读性和可调试性。我的建议是除非空间确实不够用或者面试官明确要求优化否则优先保证代码的正确性和可读性。毕竟一个能跑对的O(n)空间解法比一个跑不对的O(1)空间解法有价值得多。6.5 常见问题速查表问题现象可能原因排查方法解决方案结果偏大0-1背包遍历顺序反了打印dp数组检查是否重复使用物品容量从大到小遍历结果偏小完全背包遍历顺序反了打印dp数组检查是否限制了物品使用次数容量从小到大遍历部分用例通过边界条件错误手动计算小规模用例对比结果根据实际语义修正边界结果全错状态设计错误检查状态是否满足无后效性重新设计状态补充必要信息运行超时状态空间过大或转移复杂度过高分析时间和空间复杂度精简状态、空间优化、或用更高效的转移方式递归爆栈递归深度过大检查递归层数改用递推填表或增加递归深度限制7. 我个人在DP学习路上的一些体会动态规划这东西入门难精通更难。但它的难不是那种“看不懂”的难而是“想不到”的难。代码本身往往很短十几行就写完了但背后的思考过程可能要好几个小时。我自己的经验是学DP一定要动手。看别人的题解觉得“哦原来是这样”和自己独立推出来完全是两码事。我建议每学一个新的DP类型至少独立做五到十道同类题做到不看题解也能推出状态和转移方程为止。这个过程很痛苦但熬过去之后你会发现自己的思维方式真的变了。另外不要追求刷题数量。DP的题型是有限的经典的就那么几十种。与其刷两百道题但每道都似懂非懂不如把二十道经典题吃透每道都能讲清楚状态为什么这么设计、转移方程为什么这么写、边界为什么这么定。质量比数量重要得多。最后说一个我踩过的坑不要一上来就追求最优解。很多人看到O(n)的解法就觉得自己O(n^2)的解法拿不出手其实完全没必要。先把O(n^2)的解法写对再考虑优化。一个正确的暴力DP比一个错误的优化DP有价值一百倍。优化是锦上添花的事正确性才是底线。这篇是动态规划拆解的第一篇主要把状态设计、转移方程、边界条件、遍历顺序这些基础但核心的东西讲透了。下一篇我打算聊背包问题的几种变体以及区间DP和树形DP的入门思路。如果你跟着这篇的内容把爬楼梯、最大子数组和、最长递增子序列、零钱兑换这几个例子都亲手实现一遍那DP的基础就算是打牢了。剩下的就是多练、多想、多总结。 
长河君 · 2026/10/12 23:30:51 · 阅读 1.2k 从零拆解动态规划：状态设计与转移方程的核心思路
1. 为什么我要从零写一套动态规划拆解动态规划这四个字几乎是每个学算法的人绕不过去的一道坎。我见过太多人在面试前突击背几道背包问题、最长公共子序列的模板结果题目稍微换个皮就完全没思路。也见过有人刷了两百道DP题遇到新题还是只能干瞪眼。问题出在哪不是题刷得不够多而是从一开始就没有建立起对动态规划这门“手艺”的正确认知。我自己当年学DP也走过弯路。最早接触的是斐波那契数列的递推写法觉得不过如此后来碰到零钱兑换、编辑距离开始觉得有点意思再往后遇到状态压缩、区间DP、树形DP整个人就懵了。真正让我开窍的不是又刷了多少题而是有一天我突然想明白了一件事动态规划本质上不是一种算法而是一种思考问题的方式——它教你怎么把一个大麻烦拆成一串小麻烦然后从小麻烦的答案里拼出大麻烦的答案。这套拆解我打算分几篇来写这是第一篇重点解决三个问题动态规划到底在干什么、怎么判断一道题能不能用DP、以及最核心的——状态和转移方程到底怎么设计。我不会一上来就甩一堆数学公式而是用最直白的话和大量例子把每个概念揉碎了讲。适合谁看如果你正在学算法、准备面试、或者单纯想搞明白这个被说烂了却总也学不透的东西那这篇内容就是写给你的。哪怕你之前完全没接触过DP只要会写最基本的循环和递归就能跟上。2. 动态规划到底在解决什么问题2.1 从一个最朴素的例子说起假设你要爬一个n级的楼梯每次只能走1级或者2级问一共有多少种走法。这个问题太经典了经典到很多人一看到就知道答案是斐波那契数列。但我想让你关注的是思考过程而不是答案本身。当你站在第n级台阶上往回看你最后一步是怎么上来的要么是从第n-1级走1级上来的要么是从第n-2级走2级上来的。没有第三种可能。所以走到第n级的走法总数就等于走到第n-1级的走法数加上走到第n-2级的走法数。写成式子就是f(n) f(n-1) f(n-2)。这个式子就是所谓的“状态转移方程”。而f(n)就是“状态”它表示走到第n级台阶的走法总数。你看动态规划的核心思想在这里已经体现得淋漓尽致了当前问题的答案可以由若干个更小规模的同类问题的答案推导出来。那为什么不能直接用递归算因为递归会把同一个子问题重复计算无数次。算f(5)需要f(4)和f(3)算f(4)又需要f(3)和f(2)f(3)被算了两次。n稍微大一点计算量就爆炸了。动态规划的解决办法就是把每个子问题的答案记下来用的时候直接查表不重复算。这就是“记忆化”或者“填表”的思想。2.2 动态规划与分治、贪心的本质区别很多人分不清动态规划、分治法、贪心算法。它们确实有相似之处都是把大问题拆成小问题但拆的方式和合并的方式完全不同。分治法是把问题拆成若干个互不重叠的子问题分别求解后再合并。比如归并排序左半边和右半边完全独立排好之后一合并就完事。子问题之间没有交集所以不需要记录中间结果。贪心算法是每一步都选当前看起来最优的期望最终得到全局最优。它不管子问题之间有没有重叠也不回头检查之前的选择。贪心能用的前提是问题具有“贪心选择性质”这个条件其实很苛刻大部分问题不满足。动态规划则专门对付子问题重叠的情况。它承认子问题会被反复用到所以老老实实把每个子问题的解存起来。同时它也不像贪心那样只顾眼前而是通过状态转移方程把所有的可能性都考虑进去最终选出最优的那个。你可以这么理解分治是各干各的然后拼起来贪心是一条路走到黑动态规划是做好笔记、步步为营。2.3 最优子结构与重叠子问题动态规划能用的前提是两个性质最优子结构和重叠子问题。最优子结构的意思是大问题的最优解一定包含了子问题的最优解。拿最短路径来说如果从A到C的最短路径经过B那么A到B的那段一定也是最短的B到C的那段也一定是最短的。如果不是你换一条更短的整体不就更短了吗这就矛盾了。所以只要问题具有最优子结构我们就可以放心地从子问题的最优解推导大问题的最优解。重叠子问题的意思是在递归求解的过程中同一个子问题会被多次遇到。爬楼梯那个例子就是典型f(3)在算f(5)和f(4)时都被用到了。如果子问题不重叠那用分治就好了没必要上DP。这两个性质缺一不可。没有最优子结构你从子问题推不出大问题没有重叠子问题你记录中间结果也没意义白白浪费空间。注意很多人误以为“最优子结构”就是“局部最优能推出全局最优”这其实是贪心的思路。最优子结构说的是大问题的最优解里面包含了子问题的最优解但不代表你每一步都选局部最优就能得到全局最优。这个区别一定要想清楚。3. 状态设计动态规划最核心也最难的一步3.1 状态到底是什么如果把动态规划比作盖房子那状态就是砖块转移方程就是水泥。没有砖块水泥再多也砌不成墙。状态设计对了转移方程往往水到渠成状态设计错了怎么推都推不出来。那状态到底是什么简单说状态就是你对当前局面的一个完整描述。它必须包含足够的信息使得从这个状态出发你能做出下一步的决策并且能判断这个状态的好坏。同时状态又不能包含多余的信息否则状态空间会爆炸。拿爬楼梯来说状态就是“当前在第几级台阶”。这个信息足够了因为从第i级台阶出发你只需要知道i是多少就能决定下一步走到i1还是i2。至于你之前是怎么走到第i级的走了多少步用了什么姿势统统不重要。这就是状态的“无后效性”——当前状态一旦确定后续的决策只依赖于当前状态与到达这个状态的路径无关。3.2 一维状态与多维状态的取舍状态可以是多维的。爬楼梯是一维状态因为只需要一个变量就能描述局面。但很多问题一个变量不够用。比如经典的“零钱兑换”给你若干种面额的硬币问凑出金额n最少需要几枚硬币。这里状态是“当前需要凑出的金额”还是一维的。但如果加一个限制条件比如每种硬币最多只能用一次那状态就变成二维了dp[i][j]表示用前i种硬币凑出金额j的最少硬币数。因为你需要知道“现在考虑到第几种硬币了”和“还需要凑多少钱”这两个信息。再比如“最长公共子序列”两个字符串状态自然是二维的dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列长度。因为你需要同时知道两个字符串各自处理到哪了。那什么时候该加维度判断标准很简单如果你发现当前状态不足以做出下一步决策或者不足以判断当前局面的优劣那就说明缺信息需要加维度。但每加一维状态空间就乘一个量级时间和空间复杂度都会上去。所以要在“信息足够”和“空间可控”之间找平衡。3.3 状态的无后效性为什么重要无后效性是状态设计的一条铁律。它的意思是一旦当前状态确定了未来只与当前状态有关与怎么到达当前状态的历史路径无关。为什么这条这么重要因为如果未来依赖于历史路径那你的状态就必须把历史路径也编码进去状态空间会变得无比巨大动态规划就退化成暴力搜索了。举个例子。假设你在玩一个游戏角色有生命值和魔法值两个属性。如果你设计的状态是“当前生命值和魔法值”那没问题因为下一步能做什么只取决于当前的血量和蓝量。但如果你设计的状态是“当前生命值、魔法值、以及之前每一步的选择”那就完蛋了状态多到没法存。所以设计状态的时候一定要问自己我记录的信息是否足以唯一确定后续的决策如果两个不同的历史路径到达了同一个状态它们后续的最优决策是否相同如果相同说明状态设计是合理的如果不同说明状态里缺了关键信息需要补上。实操心得我刚开始学DP的时候经常犯一个错误——状态里塞了太多没用的信息。比如做背包问题非要把“当前背包里装了哪些物品”也记下来。其实完全没必要因为背包问题只关心“当前容量还剩多少”和“当前考虑到第几个物品了”具体装了哪些物品不影响后续决策。状态越精简效率越高。4. 转移方程从状态到状态的桥梁4.1 转移方程的本质是决策枚举状态设计好了接下来就是转移方程。转移方程说白了就是在当前状态下你有哪些选择每个选择会导致什么后果哪个后果最好用数学语言说转移方程就是dp[state] opt{ dp[prev_state] cost }其中opt是最优化操作取最大、最小、求和等prev_state是做出某个决策后到达的前一个状态cost是这个决策的代价。还是拿爬楼梯举例。状态dp[i]表示走到第i级的走法数。在当前状态i下你只能从i-1或i-2走过来。所以dp[i] dp[i-1] dp[i-2]。这里的“决策”就是“最后一步是走1级还是走2级”两种决策对应的前一个状态分别是i-1和i-2代价都是1种走法所以加起来。再拿零钱兑换举例。状态dp[j]表示凑出金额j所需的最少硬币数。在当前状态j下你可以选择任何一种面额的硬币coin。如果选了coin那你就从状态j-coin转移过来代价是1枚硬币。所以dp[j] min{ dp[j-coin] 1 }对所有满足coin j的硬币面额取最小值。你看转移方程的核心就是枚举所有可能的决策然后从中选出最优的。枚举的范围取决于问题本身但思路是通用的。4.2 边界条件别让程序在起点就翻车转移方程描述了状态之间怎么跳但总得有个起点。边界条件就是那些不需要转移、可以直接给出答案的状态。爬楼梯的边界是dp[0] 1站在地面不动就是一种走法和dp[1] 1走到第1级只有一种走法。零钱兑换的边界是dp[0] 0凑出金额0不需要任何硬币。最长公共子序列的边界是dp[0][j] 0和dp[i][0] 0任意字符串和空串的公共子序列长度都是0。边界条件看起来简单但实际写代码的时候特别容易出错。我见过太多人转移方程推得漂漂亮亮结果边界写错了整个答案全盘皆输。比如爬楼梯如果dp[0]设成0那dp[2] dp[1] dp[0] 1 0 1但实际应该是2走两次1级或者一次走2级。一个边界错误后面全错。注意边界条件一定要根据问题的实际语义来确定不能凭感觉。建议在草稿纸上手动算几个小规模的情况验证边界值是否正确。比如爬楼梯手动算一下n0,1,2,3的情况看看边界设成多少才能让结果对得上。4.3 从递归到递推两种实现路径有了状态和转移方程实现方式有两种递归加记忆化和递推填表。递归加记忆化的写法更贴近转移方程的数学形式代码通常更简洁也更容易理解。思路是写一个递归函数solve(state)先查表看这个状态有没有算过算过就直接返回没算过就按照转移方程递归计算算完存表再返回。这种写法也叫“自顶向下”。递推填表的写法是先确定状态的遍历顺序然后从边界条件开始一层一层往外推直到算出目标状态。这种写法也叫“自底向上”。它的好处是没有递归栈开销速度通常更快而且方便做空间优化。两种写法各有优劣。递归加记忆化写起来快不容易搞错遍历顺序但递归深度太大会爆栈。递推填表效率高但需要想清楚遍历顺序顺序错了结果就错了。我的建议是初学的时候先用递归加记忆化因为它的结构和转移方程几乎一一对应不容易出错。等熟练了再改成递推填表追求更高的效率。下面用爬楼梯举例两种写法都给你。递归加记忆化def climb(n, memo{}): if n 1: return 1 if n in memo: return memo[n] memo[n] climb(n-1, memo) climb(n-2, memo) return memo[n]递推填表def climb(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]你看递推版本里那个for循环的顺序就是从前往后因为dp[i]依赖于dp[i-1]和dp[i-2]所以必须先把小的算出来。如果依赖关系反过来遍历顺序就要反过来。这就是为什么递推填表需要想清楚遍历顺序。5. 实战拆解从题目到代码的完整流程5.1 案例一最大子数组和题目给一个整数数组找出一个连续子数组使得它的和最大返回这个最大和。第一步设计状态。最直接的想法是dp[i]表示“以第i个元素结尾的最大子数组和”。为什么强调“以第i个元素结尾”因为子数组必须是连续的如果dp[i]表示“前i个元素中的最大子数组和”那转移的时候你没法判断第i个元素要不要接在前面的子数组后面。而“以第i个元素结尾”这个定义天然保证了连续性。第二步推转移方程。对于dp[i]第i个元素有两种选择要么接在前面的子数组后面要么自己单独成为一个子数组。如果接在后面那和就是dp[i-1] nums[i]如果单独和就是nums[i]。我们要最大的所以dp[i] max(dp[i-1] nums[i], nums[i])。第三步确定边界。dp[0] nums[0]因为第一个元素结尾的子数组只有它自己。第四步确定答案。答案不是dp[n-1]而是max(dp[0], dp[1], ..., dp[n-1])因为最大子数组不一定以最后一个元素结尾。代码实现def max_subarray(nums): n len(nums) dp [0] * n dp[0] nums[0] ans dp[0] for i in range(1, n): dp[i] max(dp[i-1] nums[i], nums[i]) ans max(ans, dp[i]) return ans这个题还可以做空间优化因为dp[i]只依赖于dp[i-1]所以用一个变量滚动更新就行不需要整个数组。优化后空间复杂度从O(n)降到O(1)。def max_subarray_optimized(nums): cur nums[0] ans nums[0] for i in range(1, len(nums)): cur max(cur nums[i], nums[i]) ans max(ans, cur) return ans实操心得空间优化是动态规划进阶的必修课。很多DP问题的状态转移只依赖于前一层或前几个状态这时候就可以用滚动数组或者变量来压缩空间。但要注意空间优化之后代码的可读性会下降如果是在面试中建议先写未优化的版本确认逻辑正确后再提优化思路。5.2 案例二最长递增子序列题目给一个整数数组找出最长递增子序列的长度。子序列不要求连续但要求保持相对顺序。第一步设计状态。dp[i]表示“以第i个元素结尾的最长递增子序列长度”。同样强调“以第i个元素结尾”理由和上面一样。第二步推转移方程。对于dp[i]我们需要往前看所有j i且nums[j] nums[i]的位置。如果nums[i]能接在nums[j]后面那长度就是dp[j] 1。我们要最长的所以dp[i] max(dp[j] 1)对所有满足j i且nums[j] nums[i]的j。第三步边界。每个元素至少可以自己构成一个长度为1的递增子序列所以dp[i]初始值都是1。第四步答案。max(dp[0], ..., dp[n-1])。代码实现def length_of_lis(nums): n len(nums) dp [1] * n ans 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans这个题的时间复杂度是O(n^2)因为有两层循环。它还有一个O(n log n)的优化解法用到了贪心加二分查找但那个解法已经不太像典型的动态规划了这里先不展开。5.3 案例三零钱兑换题目给若干种硬币面额和一个目标金额问凑出目标金额最少需要几枚硬币。每种硬币可以用无限次。第一步状态。dp[j]表示凑出金额j所需的最少硬币数。第二步转移方程。对于金额j我们可以选择任何一种面额为coin的硬币。如果选了它就相当于从金额j-coin转移过来代价是1枚硬币。所以dp[j] min(dp[j-coin] 1)对所有满足coin j的硬币面额取最小。第三步边界。dp[0] 0凑出金额0不需要硬币。其他dp[j]初始化为一个很大的数比如无穷大表示暂时无法凑出。第四步答案。dp[target]如果它还是无穷大说明无法凑出返回-1。代码实现def coin_change(coins, amount): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for j in range(1, amount 1): for coin in coins: if coin j: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! INF else -1注意这里的遍历顺序外层循环遍历金额内层循环遍历硬币。为什么不能反过来因为每种硬币可以用无限次如果外层遍历硬币、内层遍历金额那对于每种硬币你只能沿着金额递增的方向更新一次无法实现“同一种硬币用多次”的效果。外层遍历金额、内层遍历硬币才能保证每种硬币在任意金额下都可以被重复选择。注意背包类问题的遍历顺序非常讲究。0-1背包要求每种物品只能用一次所以外层遍历物品、内层遍历容量且容量从大到小完全背包要求每种物品可以用无限次所以外层遍历物品、内层遍历容量且容量从小到大。如果搞反了0-1背包会变成完全背包完全背包会变成0-1背包。这个坑我踩过不止一次每次都要在草稿纸上画一遍才放心。6. 常见问题与排查技巧实录6.1 状态转移方程推不出来怎么办这是最常见的问题。很多人卡在这一步盯着题目发呆不知道怎么从子问题推到父问题。我的经验是不要硬推先手动模拟。拿一个具体的小例子在纸上一步一步算看看每一步的答案是怎么从前面几步的答案算出来的。比如爬楼梯你手动算n1,2,3,4,5把结果列出来然后观察规律。很多时候规律一出来转移方程就跟着出来了。另一个技巧是“从最后一步倒推”。问自己到达最终状态的前一步可能是什么把所有可能的前一步列出来然后看当前状态和前一步状态之间的关系。这个方法对很多问题都有效因为最终状态往往是问题最明确的地方。如果还是推不出来那可能是状态设计有问题。回头检查一下状态是否包含了足够的信息是否满足无后效性如果状态本身就不对转移方程当然推不出来。6.2 边界条件总是写错怎么办边界条件写错通常是因为没有想清楚“最小规模的问题是什么”。我的建议是在写代码之前先把n0,1,2,3的情况手动算一遍把结果写在纸上。然后写代码的时候用这些手动算的结果去验证边界条件。另外边界条件不一定是dp[0]或dp[0][0]。有些问题的边界是多个比如最长公共子序列dp[0][j]和dp[i][0]都是边界。有些问题的边界需要特殊处理比如零钱兑换中dp[0]0但其他dp[j]初始化为无穷大。所以一定要根据具体问题来确定边界不能套模板。6.3 遍历顺序搞反了怎么发现遍历顺序搞反的典型症状是代码逻辑看起来没问题但结果就是不对或者部分测试用例通过、部分不通过。发现的方法很简单在代码里加打印把每一步的状态值输出出来和手动模拟的结果对比。如果发现某个状态的值依赖于一个还没被计算的状态那就说明遍历顺序反了。比如0-1背包问题如果内层容量从小到大遍历那dp[j]会依赖于dp[j-weight]已经在本轮被更新过相当于同一个物品被用了多次。这时候你打印dp数组会发现结果比正确答案大因为物品被重复使用了。把容量改成从大到小遍历问题就解决了。6.4 空间优化后结果不对怎么排查空间优化之后结果不对通常是因为优化后的变量没有正确初始化或者更新顺序有问题。排查方法先写一个未优化的版本确认结果正确。然后逐步优化每优化一步就对比一次结果。如果优化后结果变了说明优化过程中引入了bug。常见的bug包括滚动数组的初始值没设对、变量更新顺序反了导致使用了新值而不是旧值、多维数组压缩成一维时索引搞错了。实操心得空间优化虽然能降低空间复杂度但会牺牲代码的可读性和可调试性。我的建议是除非空间确实不够用或者面试官明确要求优化否则优先保证代码的正确性和可读性。毕竟一个能跑对的O(n)空间解法比一个跑不对的O(1)空间解法有价值得多。6.5 常见问题速查表问题现象可能原因排查方法解决方案结果偏大0-1背包遍历顺序反了打印dp数组检查是否重复使用物品容量从大到小遍历结果偏小完全背包遍历顺序反了打印dp数组检查是否限制了物品使用次数容量从小到大遍历部分用例通过边界条件错误手动计算小规模用例对比结果根据实际语义修正边界结果全错状态设计错误检查状态是否满足无后效性重新设计状态补充必要信息运行超时状态空间过大或转移复杂度过高分析时间和空间复杂度精简状态、空间优化、或用更高效的转移方式递归爆栈递归深度过大检查递归层数改用递推填表或增加递归深度限制7. 我个人在DP学习路上的一些体会动态规划这东西入门难精通更难。但它的难不是那种“看不懂”的难而是“想不到”的难。代码本身往往很短十几行就写完了但背后的思考过程可能要好几个小时。我自己的经验是学DP一定要动手。看别人的题解觉得“哦原来是这样”和自己独立推出来完全是两码事。我建议每学一个新的DP类型至少独立做五到十道同类题做到不看题解也能推出状态和转移方程为止。这个过程很痛苦但熬过去之后你会发现自己的思维方式真的变了。另外不要追求刷题数量。DP的题型是有限的经典的就那么几十种。与其刷两百道题但每道都似懂非懂不如把二十道经典题吃透每道都能讲清楚状态为什么这么设计、转移方程为什么这么写、边界为什么这么定。质量比数量重要得多。最后说一个我踩过的坑不要一上来就追求最优解。很多人看到O(n)的解法就觉得自己O(n^2)的解法拿不出手其实完全没必要。先把O(n^2)的解法写对再考虑优化。一个正确的暴力DP比一个错误的优化DP有价值一百倍。优化是锦上添花的事正确性才是底线。这篇是动态规划拆解的第一篇主要把状态设计、转移方程、边界条件、遍历顺序这些基础但核心的东西讲透了。下一篇我打算聊背包问题的几种变体以及区间DP和树形DP的入门思路。如果你跟着这篇的内容把爬楼梯、最大子数组和、最长递增子序列、零钱兑换这几个例子都亲手实现一遍那DP的基础就算是打牢了。剩下的就是多练、多想、多总结。