动态规划这名字听着挺唬人但说白了它就是一种把大问题拆成小问题把小问题的答案记下来避免重复计算的套路。我在面试别人和带新人的时候发现很多人卡在动态规划上不是智商问题而是没人把为什么这么做讲透。这篇文章我就想用最直白的方式把这套东西掰开揉碎讲清楚从概念到经典题再到它和贪心、分治、回溯那些算法到底啥关系一次性说透。就算你是刚接触算法的新手只要跟着思路走一圈也能弄明白动态规划到底在干啥以及面试里那几道高频题到底该怎么下手。1. 动态规划的核心记住已经算过的答案别傻乎乎地重复算1.1 一个找零钱的例子看懂动态规划到底在干嘛先别急着背书上的定义我直接给你扔一个问题你有1元、3元、4元三种面值的硬币现在要找给客户6元钱问最少需要几个硬币你可能会想那我先用4元剩2元2元只能用1元凑那就是411一共3枚。但如果你先用3元剩3元再凑一个3元那就是2枚。3枚比2枚多所以答案应该是2枚。那这题跟动态规划有什么关系你仔细想想你在算凑6元最少几个硬币的时候其实你已经不自觉地在算更小的数了。你算6元之前得知道5元、3元、2元各需要几个硬币。而这些更小的数你在算别的组合时又得重复用。动态规划的思路就是我不傻乎乎地每次重新算我开一个表把凑1元需要几个凑2元需要几个统统记下来算大的数时直接拿小的数来用。这个记住已经算过的小问题答案的做法就是动态规划的核心。它解决的问题也很典型一个问题可以拆成互相重叠的子问题而且最终答案能从子问题的最优解推出来。用术语说就是两个性质最优子结构和重叠子问题。后面我会展开讲。1.2 斐波那契数列最简单的动态规划骨架斐波那契数列你应该不陌生第1项是1第2项是1第n项等于前两项之和。写成公式就是f(n) f(n-1) f(n-2)。如果让你写个函数计算f(10)新手最容易写出这样的递归def fib(n): if n 2: return 1 return fib(n-1) fib(n-2)这写法对不对对。但效率惨不忍睹。你算f(10)的时候它会去算f(9)和f(8)算f(9)的时候又去算f(8)和f(7)。你会发现f(8)被算了两次f(7)被算了好几次越小的数被重复计算的次数越多。这就像你准备考试同一页书翻来覆去背了八百遍浪费时间。动态规划的做法就聪明多了我从第1项开始一项一项往后推每次都用已经算好的结果来算新的def fib_dp(n): if n 2: return 1 dp [0] * (n 1) dp[1] 1 dp[2] 1 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]这就是一个标准的动态规划解法。它用了一个数组dp来记录每个子问题的答案从最小的子问题开始一步一步推到最终答案。时间复杂度从递归的指数级降到了O(n)一个天上一个地下。1.3 动态规划的两个必要条件最优子结构和重叠子问题我把刚才那两小节的共性提炼一下就两个词重叠子问题和最优子结构。这两个是判断题目的关键也是面试里经常被追问的为什么这题能动态规划。重叠子问题说的是一个大问题在拆解过程中会反复遇到相同的小问题。斐波那契里的f(8)被反复计算就是典型的重叠子问题。如果一个问题的子问题完全不重叠比如归并排序那种每次拆出来的子问题都是新问题那动态规划就没用武之地了。最优子结构说的是大问题的最优解可以从子问题的最优解直接拼出来。还是拿找零钱来说凑6元的最少硬币数如果最后选择了一个3元硬币那剩下的就是凑3元的最少硬币数只要凑3元的子问题是最优的加上这1枚硬币就是凑6元的最优。这种局部最优能推导全局最优的性质就是最优子结构。判断一道题能不能用动态规划你只需要问自己两个问题拆出来的小问题会不会重复出现大问题的最优解能不能由小问题的最优解组合出来两个答案都是能那就放心大胆用DP。2. 动态规划的三个核心特点和解题套路2.1 三个核心特点从状态定义到递推再到记忆化动态规划有三个标志性的特点你在判断一个解法是不是动态规划时就是看这三样。第一有明确的状态定义。你得说清楚dp[i]到底代表什么。是凑i元钱需要的最少硬币数还是前i个物品能装的最大价值这决定了整个算法的走向。我见过很多新手栽在这里状态定义得含含糊糊后面全乱套。第二有状态转移方程。就是明确dp[i]怎么从之前的某个dp值算出来。找零钱的转移方程是dp[i] min(dp[i - 1], dp[i - 3], dp[i - 4]) 1。斐波那契的是dp[i] dp[i-1] dp[i-2]。转移方程是动态规划的发动机写不出来这题就做不了。第三有边界条件和记忆化存储。边界条件就是最小的问题答案是啥比如dp[0]是0dp[1]是1。记忆化就是这个dp数组本身它把计算结果存下来之后要用的时候直接查表而不是重新递归计算。如果你是用递归加备忘录实现动态规划这就叫自顶向下如果你从dp[0]开始往大推这叫自底向上。两种都能写出正确答案自底向上的写法通常更稳因为没有函数调用的开销也基本不会爆栈。2.2 动态规划的实战六步走从读题到码代码的完整套路光说概念没用我来给你一个能直接套用的做题套路。这是我自己刷了数百道DP题之后总结出来的也是我带人时必讲的一套流程。第一步读完题目先别急先把最后要求的东西写成一个函数表达式。比如求凑n元钱需要的最少硬币数那你的目标就是算一个值这个值关于n存在某种递推关系。第二步定义dp数组的含义。写清楚dp[i]表示的是什么东西。这里有个心法dp的含义越具体后面写转移方程越简单。第三步推导状态转移。这一步是核心中的核心也是最讲究的地方。核心思路是站在dp[i]这个点往回看一步想想最后一步做了什么。找零钱里最后一步是花了1元、3元还是4元背包里最后一步是装了第i个物品还是没装。第四步找边界条件。想想最小的问题是什么样的比如dp[0]、dp[1]应该是多少。这一步别偷懒很多崩溃的bug都出在边界条件上。第五步确定遍历顺序。这步看上去不起眼但真的特别关键。有的是从前往后有的必须从后往前一弄错结果就乱了。后面讲背包问题时会专门演示教训。第六步根据思路码代码然后用一个小规模的测试用例验证。验证这一步很多人不做或者只在脑子里过一遍。我强烈建议你真跑一跑肉眼盯着dp数组走一遍很多隐藏bug一下就现形了。2.3 动态规划在不同领域的变体状态压缩、区间DP和树形DP如果你已经能熟练处理基础题那动态规划的花样还有很多。我看热搜词里有车辆动态规划问题实际上动态规划的应用领域远比你想的宽广我来给你简单过几个常见的变体让你知道它不止是刷题用的。区间DP这种题目的状态定义不是一维的而是dp[i][j]表示从i到j这个区间的最优解。典型应用是矩阵连乘、括号匹配、回文串切分。它的转移思路一般是想最后一步是把这个区间切成两半切在哪儿最优。树形DP状态定义在树的节点上通常有dp[u]表示以u为根的子树的最优解。典型的应用有树的最大独立集、树的直径、打家劫舍的树形版本。它的特点是需要在树上做DFS从叶子往根推。状态压缩DP适用于n特别小大概十几到二十几但状态组合爆炸的问题。典型的像旅行商问题、铺砖问题。它是用一个二进制数表示哪些元素已经用过这个状态然后在这个bitmask上做DP。这个确实烧脑但玩明白了非常上瘾。动态规划在工程领域也很能打。拿车辆路径规划来说物流配送的车队要怎么安排路线配送成本最低天然就是一套组合优化问题而其中的动态规划思路就是按当前几辆车已经派到第几个客户来分层决策。无人机路径规划也有类似的建模方式。所以你学DP不只是为了面试它真的能解决实际工程里的复杂决策问题。3. 经典例题一0-1背包问题3.1 题目描述和暴力思路为什么不行0-1背包问题可以说是算法面试的钉子户也是我在热搜词里看到的高频词。题目长这样有一个容量为C的背包给你n件物品每件物品重量为w[i]价值为v[i]现在要从这些物品里选一些装进背包要求在总重量不超过C的前提下让总价值最大。每件物品要么选要么不选不能只拿一半这就是0-1的含义。我们先用直白的方式尝试暴力解每件物品都有选和不选两种决策n件物品就有2的n次方种组合。如果n只有101024种情况暴力枚举完全可以但如果n是30大约10亿种情况n是50计算机就跑不完了。在实际生产中物品数往往成百上千暴力解法直接歇菜。这就是动态规划出场的场景。你想一下物品多不值怕因为它们本质上有很多重复子问题——处理第i件物品时无论前面的具体选了哪些关键只在于剩余背包容量还剩多少以及到第几件物品为止。重复出现的就是这两个参数所以就可以建一张二维表用DP处理。3.2 标准二维DP解法状态定义和转移方程我们直接动手。定义状态dp[i][j]表示前i件物品背包容量为j时能装下的最大价值。这个定义你可以直接背下来用它是背包问题的经典状态定义。接下来推导转移方程。在处理第i件物品时我们面临两个选择选择一不装这件物品。那前i件物品的最大价值就等于前i-1件物品在容量j下的最大价值也就是dp[i][j] dp[i-1][j]。选择二装这件物品。那前提是背包容量够即j w[i]。装进去之后价值等于前i-1件物品在剩余容量j-w[i]下的最大价值再加上v[i]也就是dp[i][j] dp[i-1][j-w[i]] v[i]。我们要的是两条路里的较大值所以转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。注意这里有一个细节非常关键方程里用的是前i-1件这意味着处理第i件物品时不能使用已经装了第i件之后影响过的状态。这是后面一维优化的核心逻辑我们马上讲。3.3 一维数组优化为什么必须从后往前遍历二维dp的空间复杂度是O(n*C)。当n和C都比较大时比如n2000、C10000那就会开一个2000万大小的数组占用大量内存。但你看转移方程dp[i][j]只依赖dp[i-1][...]这一行。那我们可以偷懒只保留一行边算边覆盖。这就是滚动数组优化。但这里有个大坑如果你从前往后遍历容量j你会发现当你算到j比较大时dp[j-w[i]]可能已经被这一轮计算覆盖了不再代表前i-1件的答案了。这就导致一个物品可能被装多次完全违背了0-1的约束。我以前带新人时经常说你如果非要看看从前往后会发生什么就想象一个容量足够的背包某个物品会被你反复塞进去最后价值算出来虚高一大截。从后往前遍历就完美避开了这个问题——因为j-w[i]始终小于j从后往前时较小的j还没被更新它还是上一轮的旧值正好是我们要的前i-1件的答案。标准的一维实现长这样def knapsack_01(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]这段代码在LeetCode 416题、494题里都能直接套用建议你自己动手敲一遍把dp数组的中间过程打印出来你就能彻底理解为什么要从后往前。3.4 背包问题的混血变种完全背包与多重背包0-1背包的兄弟是完全背包每件物品可以无限取。这个问题的代码跟0-1极为相似唯一区别是遍历容量时改成从前往后。我们刚才说从前往后会导致一件物品被取多次这在完全背包里反而是我们想要的特性。一个小的遍历顺序改动就能切换问题模型这也是动态规划精妙得很的地方。多重背包则介于两者之间每种物品有限定数量。常见的优化套路有二进制拆分就是把取k件某物品拆成取1件、2件、4件...的组合从而转换成0-1背包。这个技巧如果在面试中能主动讲出来属于明显的加分项。这三种背包是递进关系。我建议你学的时候先老老实实把0-1背包的二维和一维写法都写明白再看完全背包和多重背包。它们理解了再去看一些工业界的背包变种应用比如资源分配、预算优化问题就非常顺手。4. 经典例题二最少硬币问题和路径规划问题4.1 最少硬币问题一维DP的入门必做题最少硬币问题在热搜里也出现了动态规划最少硬币python它的题目描述是你有若干面值的硬币比如coins [1, 3, 4]和一个总金额amount求凑出这个金额最少用几个硬币。如果凑不出来返回-1。这就是开头的找零钱问题。我们的状态定义是dp[i]表示凑出金额i最少需要多少个硬币。对每个金额i我们试着把最后一枚硬币设成所有可能的面值c并且c要小于等于i那么dp[i] min(dp[i - c] 1)。翻译成人话就是我先凑出(i-c)再加一枚c硬币。边界条件dp[0] 0凑0元自然不需要任何硬币。初始时把所有dp[i]设成一个很大的数比如正无穷表示暂时凑不出来。实现代码def coin_change(coins, amount): 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这个题和斐波那契不同因为金币面值不固定所以内层需要一次循环尝试所有面值。它的递推关系是每步都选择最后一枚硬币的最优面值。复杂度是O(amount * len(coins))对于一般场景完全够用。4.2 从最少硬币到车辆路径规划二维DP打通关车辆动态规划问题这个词其实挺宽泛的。它可以是物流里的车辆路径最短问题也可以是自动驾驶里的轨迹规划但核心思想都是把总体的复杂优化拆成阶段决策。我给你举一个简化的路径规划例子假设有一辆配送车需要从0号点出发依次经过若干个客户点最终返回仓库要求每个客户点都被访问一次且总路程最短。当客户点数少比如小于15时这就是典型的旅行商问题可以被状态压缩DP解决。状态定义可以是dp[mask][i]表示当前已访问的客户集合是mask且最后停在客户点i时走过的最短距离。这里的mask是一个二进制数其中第k位为1表示第k个客户点已经访问过。转移时从任意一个已访问点i往一个还没访问的点j走就更新dp[mask | (1j)][j]。这种思路在工程里是非常实用的比如外卖平台给骑手派单时规划取餐配送顺序物流公司规划城市内多据点配送路径甚至在一些仓储机器人的调度中都能看到类似原理。你把这个二维DP想明白了出门跟人聊调度算法都有底气。4.3 实战对比最少硬币与背包问题的异同最少硬币和背包问题都属于典型的背包家族但侧重点不同。背包是在容量限制下最大化价值硬币是在金额约束下最小化数量。一个是max一个是min但底层的DP框架完全一致都是枚举决策选最优。但也有个显著区别硬币问题不涉及容量这种二维状态因为硬币价值本身就是金额所以是一维DP背包涉及二维约束物品维度和容量维度所以通常是二维DP。这也提醒我们一个重要经验DP状态维度的数目通常由决策时的约束条件个数决定。约束越多维度越高代码也越复杂。如果你把这两道经典题都弄透了你已经可以应付大量中低难度的面试题了。LeetCode上有不少DP题就是从这两题模型换了个马甲比如分割等和子集就是背包变种爬楼梯就是斐波那契变种零钱兑换II就是背包方案数问题。万变不离其宗。5. 动态规划和其他算法思想的比较5.1 动态规划 vs 分治看起来像其实差在重叠上动态规划最容易和分治法搞混因为分治法也是拆大问题为小问题再合并答案。归并排序、快速排序、二分查找等都是分治法。它们最本质的区别就是分治法拆出来的各个子问题之间通常是相互独立的左边排序不会用到右边排序的结果而动态规划拆出来的子问题大量重叠子问题A的答案要被子问题B、C反复使用。这么说可能还是抽象我拿一个生活例子对比打扫一套三室一厅的房子。分治法就是把客厅、主卧、次卧分配给三个人各自清扫最后汇总卫生情况互相不打扰动态规划则是整个房子的整洁度取决于每一间房间的整洁度而你可能反复进出每个房间好几次所以干脆记住每间房已经打扫到什么程度避免重复干活。实际写代码时分治法往往用递归实现子问题互不影响动态规划则用表记录子问题结果。有些算法题确实既可以用分治也能用DP比如求连续子数组最大和分治法也能O(nlogn)解但DP的O(n)显然更香。5.2 动态规划 vs 贪心算法贪心是DP的怕麻烦版贪心算法和DP有很多相似之处都是做多步决策都要求在局部选择中做出最优判断。但是贪心算法只做一次选择就不回头了——每一步都选当前看起来最好的绝不重新考虑之前的选择。我举一个例子你马上就能分清要找零钱假设硬币面值是[1, 5, 11]要凑15元。贪心会先拿11剩4再拿4个1一共5枚。但实际上最优是3个5元一共3枚。贪心在这里栽了跟头因为它目光短浅只看到了第一步的最大面值。动态规划则会把所有组合都纳入考量算出真正的最优解。所以结论是贪心算法是DP的特殊情况在每一步的局部最优选择能保证全局最优时才成立。如果题目有选择任意面额可以取多次之类需要全局权衡的约束贪心多半会错。当然贪心的优点是快O(n)甚至O(nlogn)就完事了所以面试时如果题目允许可以先尝试贪心不行再上DP。5.3 动态规划 vs 递归 / 回溯 / 暴力枚举递归和DP本身不是对立的DP的自顶向下写法就是递归加备忘录。但纯递归的问题是会重复计算大量子问题。回溯算法则是一种深度优先搜索的穷举式思路它会尝试每一种可能性走不通就回头。理论上回溯也能解决DP的题目但你想想n30时2的30次方的组合数回溯根本跑不动。所以回溯适合的是只需要一个解或者搜索空间非常小的问题比如走迷宫、排列组合、N皇后问题。动态规划的优势就是把穷举的空间压缩了。以背包为例回溯的复杂度是O(2^n)DP的复杂度是O(n*C)从指数级降到多项式级这是一个质的飞跃。是的DP也不可能跑赢所有情况它只是把一部分组合过程用合并子问题的方式省掉了。这个对比能帮你构建完整的算法认知暴力枚举是底线回溯是枚举的带剪枝升级版贪心是肉眼可见的单向最优分治是把独立的小问题递归答案合并DP则是记录重叠子问题答案的最优决策框架。每个算法都有它的适用边界没有银弹。5.4 动态规划 vs 搜索算法和工程实践选择工程里还有一种常拿来和DP比较的思路——启发式搜索比如A*算法、遗传算法。这类算法在解空间巨大、没有确定性多项式解的时候很好用比如大规模车辆路径问题。它们能很快给出一个不错的解但不保证全局最优。DP则保证在状态空间可枚举、转移函数明确时给出精确最优解。选型的时候我的个人经验是能建出明确状态转移方程、且状态数量可控的优先用DP如果状态空间大到不可枚举比如上百个节点的路径规划那就放弃精确解转向启发式或者混合策略。很多物流调度系统实际上是先用DP求解小规模骨干网络再用启发式算法处理大规模随机需求两者的结合才是工业界常态。在代码实现层面DP不一定比搜索写起来更快。有的题目你觉得是DP但状态定义很别扭转移方程推不出来这时候用BFS或者DFS加剪枝反而更快也是一种明智选择。算法选型任何时候都是够用就好不要为了用DP而用DP。6. 动态规划实战笔记状态定义、边界条件与遍历顺序的坑6.1 状态定义不清是最大的坑学会换一种表达方式我在实际写代码和Code Review中见过最多的动态规划翻车现场基本都是同一个原因状态定义没想清楚就开写。比如背包问题有些新手会把dp[i]定义成第i件物品的最优价值结果写来写去根本没法满足容量约束正确的定义里必须包含前i件和容量j两个维度。判断一个状态定义好不好的标准很简单能不能用一句话讲清楚dp[i]或dp[i][j]是什么意思能不能从它的语义推导出转移方程如果你跟旁边人讲到一半自己都绕进去了那定义大概率是有问题的。这时候别急着码代码回到草稿纸上重新定义把最后一步做了什么写出来通常就能理清思路。我之前带过一个同学卡在打家劫舍题上他定义dp[i]为偷前i个房子的最大金额但转移时又不确定能不能偷第i家。我让他换一个表达方法改成偷到第i个房子时最多能偷到多少且第i个房子可偷可不偷然后把可偷可不偷的标志再拆成一个二维状态。他一下就通了。说明换表达方式这个建议是真的有用。6.2 初始化与边界条件的常见错误从0开始和从1开始的迷思边界条件里的误区也很经典。有一类数组类DP题状态从0还是从1开始会直接影响代码的边界判断。我的建议是如果你从1开始遍历数组长度就开n1dp[0]表示空状态如果你从0开始遍历一定要认真处理i0时的含义。两种都可以但一旦选定就要从头到尾保持一致。对于最小值类问题初始值一般设为正无穷对于最大值类问题初始值设为0或负无穷。很多新手初始值设得不对比如求最少硬币数时把dp都设成0那后面一直min都是0答案全错了。所以初始化前先问自己dp[i]在还没有算出来之前应该是一个不可能达到的糟值还是一个空状态的基值6.3 遍历顺序决定一切一维滚动数组的正反遍历技巧我们前面已经两次提到遍历顺序了这里我再强调一遍因为这是我最常被问的问题。当dp是一维滚动数组时如果转移依赖的是上一个状态比如dp[i-1][...]也就是说不能在本轮被覆盖那么就必须从后往前遍历如果转移依赖的是当前状态更小的情况比如完全背包可以把一件物品无限使用那就可以从前往后遍历。但这句话不是死记硬背的我教你一个判断方法在每次内层循环更新dp[j]前想一下dp[j]用的旧值是哪一轮的。如果dp[j - w[i]]应该是上一轮物品决策完的值那它就必须是还没被本轮的循环更新过的旧值。肉眼无法确定性判断的话我建议先在小数据上跑一遍把dp数组的每轮更新打印出来一眼就能看出遍历方向错了没有。6.4 多维度DP把二维状态扩展到三维甚至更高当你掌握了基础的二维dp之后会遇到一些需要三维状态的题目。比如有额外预算约束的背包或者必须且只能选恰好k件的选择问题。这时候dp[i][j][k]表示前i件物品容量j已选k件的最优值。状态维度增加后代码复杂度呈指数上升但核心思路不变你的状态里需要记录每一个独立的决策约束。我见过一个工程中的例子——排班问题里同时考虑员工技能等级、工作时长上限和任务优先级三个约束最终用了三维DP才把问题收敛到可解范围。这类问题写起来容易乱我建议代码里给每一维都写上注释甚至在变量名里就体现出来比如dpByItemByCapByCount。6.5 空间优化技巧滚动数组之外还有状态压缩除了把二维dp压缩成一维滚动数组还有一种更狠的优化叫状态压缩。当状态维度很多但每一维的取值范围都很小比如只有0/1两种可能时你可以用一个整数表示一整组状态。这听起来高端其实原理就是二进制位运算。每个bit表示一种决策选择一个int就能表达32个物品的选择状态。状态压缩最经典的例子就是旅行商问题还有LeetCode上的一些铺地板问题。实现时需要用到位运算技巧判断第k位是否为1mask (1k)、把第k位设为1mask | (1k)。这类题目的思维跨度确实大但一旦你掌握了很多看似复杂的组合优化问题都能迎刃而解。这也是我在车辆动态规划热词里第一时间想到状态压缩的原因——车辆路径规划的核心数学模型在状态空间可控时就是用状态压缩DP解的。7. 动态规划的进阶应用场景与现实价值7.1 在面试中的高频考点和刷题策略如果你在准备算法面试动态规划绝对是不能绕过的一座大山。我统计过一些主流公司的面试题DP相关题目的出现频率大概能排进前三。常见的考察方向就是斐波那契变种爬楼梯、打家劫舍、背包问题分割等和子集、目标和、最长子序列问题最长递增子序列、最长公共子序列、区间DP戳气球、矩阵连乘、编辑距离等。我的建议是不要一上来就狂刷难题按模块突破效果更好。先把一维线性DP做到烂熟再攻克二维DP接着过渡到背包体系最后再碰区间、树形、状态压缩这些进阶版本。给自己定一个目标能从状态定义、转移方程、边界条件三个维度把每道DP题讲清楚哪怕不会写代码面试的临场表达能力也会好很多。7.2 在自动驾驶、物流调度和生物信息学中的应用动态规划绝不只是书本知识。在我熟悉的工程领域自动驾驶里的路径规划算法经常把全局路径拆成一段段的局部轨迹优化问题每一段的最优决策会被缓存下来供后续路段参考这正是动态规划的思想。物流领域车辆路径规划中配送员的接单顺序选择、装载空间分配也都建立在DP的数学模型之上。生物信息学里的DNA序列比对比如编辑距离更是经典中的经典人类基因测序比对工具里就有大量DP算法在跑。如果你未来做后端开发、推荐系统或基础架构DP的思维同样有用。推荐系统里的资源分配和预算消耗控制本质上也像一个多维背包问题。所以我常说学会DP受益的不只是算法题而是你面对一切多阶段决策优化问题的思路。7.3 动态规划的局限性当然动态规划也不是万能的。它最大的局限就是状态空间爆炸一旦问题的维度变大状态数量就会指数增长内存和时间就都扛不住了。这就是为什么现实中很多问题需要启发式算法来替代DP。其次DP要求问题具备最优子结构也就是说每个子问题最优合起来才是全局最优但很多真实问题并不满足比如某些涉及多个目标互相牵制的多目标优化问题。遇到这种情况不要硬套DP。先分析问题的约束和不变量的数量如果状态数在可接受范围就尝试DP否则就要引入贪心蒙特卡洛搜索整数规划或者深度学习等更复杂的方法。算法选型和人生选专业一样都是要明确边界、发挥优势。在写这篇文章的最后我想说一个我个人的体会动态规划学到最后你会发现最难的不是记住一堆模型而是把陌生问题翻译成自己熟悉的状态定义。这种翻译能力只能靠大量刻意练习来磨。如果你刚开始学可以在看完每一道例题后尝试把题目的描述换成自己的话再写一遍状态定义隔一天不看答案重写一遍代码效果会非常明显。希望这篇文章能帮你在动态规划这条路上少走些弯路早日享受到那种万变不离其宗的通透感。