★ FEATURED ARTICLE 一看到“动态规划”四个字很多刚开始刷算法题的朋友都会心里咯噔一下。这个词乍一听高深让人以为是什么玄之又玄的数学理论后来我花了不少时间才想明白动态规划本质上就是把一个复杂问题拆成一层层有关系的子问题先算小的再慢慢拼成大的同时把已经算过的结果存下来。想通这一点之后你再回头去看那些经典题会发现它们就像同一个模板印出来的。这篇文章我想从一个老算法工程师的角度谈谈我理解的动态规划核心原则、从暴力递归优化到DP的标准路径以及0-1背包这类经典题的完整思考过程最后把实操里踩过的坑都摆出来。适合正在学算法、准备面试的开发者看也适合那些看答案能看懂、自己动手就卡壳的朋友。1. 动态规划到底在解什么题1.1 一句话讲清核心逻辑动态规划最朴素的描述是把一个大问题划分成一组互相之间有依赖关系的子问题先解决最小的问题再把答案一层层往上“递推”凑出最终答案。注意这里说的是“有依赖关系”这一点和普通分治不一样。分治的子问题通常是彼此独立的比如归并排序把数组分成两半各自排序后再合并就行而动态规划解决的子问题往往会重复出现比如计算斐波那契数列时F(5)会反复用到前面的某个值如果每次都从头算就会浪费大量时间。我用生活化的例子来记你要从一楼爬上五楼每次可以走1级或2级台阶问一共有多少种走法。这是一个典型的一维DPF(n) F(n-1) F(n-2)。为什么是这个式子因为到达第n阶的最后一步要么从n-1阶跨1级上来要么从n-2阶跨2级上来。它把一个大问题拆成了两个更小的子问题而且这两个子问题在递归过程中还会被反复计算。这就是动态规划最核心的“重叠子问题”——同一个子问题被多次求解所以值得把结果存起来。再说“最优子结构”。一个问题是求最值的场景下全局最优解往往可以由子问题的最优解组合出来。比如你从起点走到某个格子路径代价最小时那么到达终点前一步的格子也必须是以最优路径过来的。这样的性质就叫最优子结构。有最优子结构不一定是DP题但缺少这个性质大概率是做不了DP的。1.2 它和递归、贪心、分治的区别很多人会把动态规划和记忆化递归彻底划等号其实可以这么理解但DP的常规形态是自底向上填表。记忆化是自顶向下靠递归加备忘录DP是反过来先把最小状态算清楚再一层层累加。两者解决问题的集合基本一致只是实现方式不同面试里更常见的是让你写出自底向上的版本因为性能稳定不依赖递归栈。方法核心思想适合场景典型问题暴力递归枚举所有可能规模极小全排列、子集生成贪心每一步取当前最优局部最优等于全局最优部分硬币问题、活动选择分治子问题独立各自求解再合并无重复子问题归并排序、二分查找动态规划重叠子问题状态递推记录已算结果有重复子问题且有最优子结构背包、编辑距离、路径规划关键区别在于贪心不做回溯一旦决定就不会改DP会在所有可能的决策中做取舍。分治的子问题是一棵树DP的子问题是一张有依赖的图。如果你在递归过程中发现同一个函数被以同样的参数调了很多次那基本就可以考虑DP了。1.3 为什么叫“动态”规划“Dynamic Programming”这个名字容易吓唬人其实和“动态”这两个字的关系很大指的是多阶段决策过程。你每一步需要根据当前状态做一个决策而这个决策会改变状态状态一变下一步的决策空间也跟着变整个过程是动态演进的。至于“Programming”这里并不是写代码的意思而是指一种规划方法相当于为一连串的决策制定方案。我习惯用“拨号导航”来类比你从一个路口出发每个路口都要选择走哪条路一旦选了你所在的位置就变了下一个路口的选择又取决于新位置。每一步“当前在哪”就是状态每一步“下一步走哪条路”就是决策。动态规划就是帮你把这条路径上所有路口的最优答案都记下来最后拼出整条最优路线。讲到这还要带出一个概念无后效性。当你站在某个状态时只需要知道“当前状态是什么”以及“当前能做什么决策”不需要回头关心过去是怎么走到这里的。这个性质很重要后面判断一道题能否用DP这个是关键标准之一。2. 从暴力递归到DP一条可复制的三步路径2.1 先写最朴素的递归我建议每次遇到一道新题先别急着想状态和转移方程直接写出最不用脑子的暴力递归版本。用爬楼梯来演示def climb(n): if n 2: return n return climb(n-1) climb(n-2)这个版本的逻辑完全正确但时间复杂度是O(2^n)。你试一下n40本地跑起来已经很卡了。原因在于它把同一个子问题算了很多次比如F(4)会被F(5)和F(6)各算一次。画一棵递归树你会看到大量重复节点。为什么先写暴力因为暴力递归就是“状态定义”的雏形。递归函数的参数往往就是状态返回值往往就是dp值。比如climb(n)的参数n对应的就是dp[n]的下标它的返回值就是dp[n]应该存的内容。从这个结构出发后面改造成DP会很自然。很多人觉得一上来就写出漂亮的状态转移方程很难其实就是因为跳过了这一层思考。2.2 加一个数组记忆化搜索既然重复计算浪费时间那就把算过的结果存起来。加一个数组cache初始化为-1表示没算过def climb_memo(n, cache): if n 2: return n if cache[n] ! -1: return cache[n] cache[n] climb_memo(n-1, cache) climb_memo(n-2, cache) return cache[n]复杂度从指数级降到O(n)。这一步的关键是递归结构不变只是多了个缓存。它叫“自顶向下DP”也叫记忆化搜索。如果题目本身递归就很容易写先写记忆化也能保底拿到大部分分数。但是要注意递归深度过大会爆栈。比如n等于10万甚至更大再用递归实现很可能直接Runtime Error。所以面试里更稳的版本是自底向上的迭代DP。记忆化搜索的价值更多在于帮你理清状态和转移关系尤其在做区间DP或树形DP时它的代码往往比自底向上更容易写对。2.3 变成填表DP再把空间省下来自底向上其实就是在模拟记忆化搜索的填表过程先算最小状态再按顺序往后推。def climb_dp(n): if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]进一步观察dp[i]只用到了dp[i-1]和dp[i-2]所以连数组都可以不要用两个变量滚动更新def climb_dp_opt(n): if n 2: return n a, b 1, 2 for _ in range(3, n 1): a, b b, a b return b这就是空间状态压缩的原始形态。很多DP题都能做类似的压缩比如0-1背包的二维表压成一维。空间优化不是必要操作但能体现你对状态依赖关系的理解程度面试时主动提出来会是加分项。3. 0-1背包实战一次把状态转移吃透3.1 问题模型与状态定义我们来看一个非常典型的0-1背包问题有n件物品每件物品有自己的重量和价值现在有一个容量为capacity的背包每件物品最多选一次问能带走的最大总价值是多少。“0-1”的意思是每件物品要么拿要么不拿不存在拿半件的情况。为什么贪心不适用直观上你可能想优先拿单位重量价值最高的物品。我举个反例三件物品的重量是10、20、30价值是60、100、120背包容量50。单位重量价值分别是6、5、4按贪心应该选重量10和20总价值160但最优解是选重量20和30总价值220。因为每件物品占用不同的容量局部最优拼不成全局最优。这就是背包问题不能贪心的原因。接下来定义状态dp[i][j]表示“只考虑前i件物品时背包容量为j的情况下能获得的最大总价值”。注意这里的“前i件”可以理解为已经处理完第1到第i件第i件对应数组下标i-1。如果你把下标定义绕晕了后面转移方程一定写错。所以我习惯统一物品数组从0开始但dp的行从1开始第0行代表空物品集合。3.2 推导转移方程第i件物品下标i-1面对容量j只有两种决策不装它或装它。不装它结果就是dp[i-1][j]装它需要先留出weights[i-1]的空间所以收益是dp[i-1][j-weights[i-1]]再加上values[i-1]。取两者的最大值。if j weights[i-1]: 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]整个二维表就是从第0行开始逐行向上填。第0行全是0因为没有物品时价值必然是0第0列也全是0因为没有容量时什么都装不了。这个例子再次说明状态转移方程不是凭空蹦出来的它描述的就是“当前这一件物品到底放不放”这一组决策。这里我特别想说一点状态定义决定转移方程的形态。如果定义成“容量j能装的最大价值”转移就是上面这个如果定义成“剩余容量r能装的最大价值”转移方程方向会反过来但本质一样。面试时先把状态定义说清楚再看它怎么写比闷头硬调简单太多。3.3 二维转一维循环方向的秘密观察二维的递推式每一行i只依赖上一行i-1也就是说我们根本不需要保留整个二维表只需要上一行的数据。用一维数组dp[j]反复覆盖就可以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]很多初学者第一次写一维背包时都是顺手写成正序结果答案错了却找不到原因。为什么必须倒序因为正序时dp[j - weights[i]]可能已经在本轮外层循环中被当前物品更新过了这意味着同一件物品被用了多次。举个具体例子一件物品重量1、价值3容量2。正序更新j1时dp[1]3j2时用dp[1]3去更新dp[2]6这等于拿了两次这件物品。倒序遍历时j2先更新j1还没被当前物品污染所以结果是3正确。这个细节就是0-1背包和完全背包的核心区别。另外提醒一下如果用的是二维dp那么外层循环i和内层循环j的先后顺序对结果没有影响因为每一行只依赖完整的前一行。但一维dp的循环方向和外层循环顺序必须严格按标准写一旦乱了结果就很难看。3.4 背包问题的常见变形背包家族远不止这一种。完全背包允许每件物品取无限次代码上只改动一点一维循环改成从0到capacity正序遍历含义就完全不同它表示同一件物品可以反复更新当前行。多重背包每种物品有数量上限常见做法是二进制拆分把每件物品按1、2、4、8等数量拆成新的物品再套0-1背包。还有带费用维度的二维背包要在dp里再加一维表示另一种限制有要求恰好装满的背包初始化时要把不合法状态设置成负无穷有求方案数的背包转移方程从max变成累加。这些东西本质上都是在0-1背包的状态和边界上做文章建议先把0-1背包彻底吃透再一步步扩展。4. 拿到题目怎么判断该不该用DP4.1 三个判据最优子结构、重叠子问题、无后效性面试或者刷题时一道题拿到手怎么快速判断该不该往DP方向想我习惯用三个特征去卡。最优子结构全局最优解可以由子问题的最优解拼接出来。比如要从左上角走到右下角找最小路径和走到终点前一步要么是从上方来要么是从左方来那么只要上方和左方各自的最小路径和已知终点的值就很容易算出。注意这里说的“拼接”不一定是指相加更多是指一种组合关系。重叠子问题递归过程会反复遇到同样的子状态。很多题目一眼看不出重叠画几层递归树就能发现。比如最长公共子序列对两个字符串做递归搜索大量调用路径是重复的推导过程中你会发现同样的“剩余子串”组合出现了很多次。无后效性一旦当前状态的值确定接下来怎么走只依赖这个状态值而不依赖过去的具体路径。我拿棋盘举例无论你之前怎么走到格子(2,3)只要现在站在(2,3)并且已经知道到它的最优代价下一步怎么走就只和(2,3)有关和你是从上边来还是从左边来没有关系。如果某道题需要回看历史步骤才能做决策那就不能直接用标准DP。4.2 一张表看懂常见DP题型类型特征线索典型问题状态定义习惯线性DP一维数组逐个元素转移最大子数组和、最长递增子序列dp[i]表示以第i个元素结尾或前i个元素的结果区间DP需要枚举区间左右端点石子合并、最长回文子序列dp[i][j]表示区间[i, j]的最优结果背包DP有重量/体积和容量限制0-1背包、完全背包dp[i][j]表示前i件物品装入容量j的最大价值树形DP依赖树结构父节点由孩子转移树上最大独立集dp[u][0/1]表示节点u选或不选的状态状态机DP同一时刻有多个状态互相转移股票交易问题dp[i][0/1]表示持有或未持有状压DPn很小但子集枚举量大旅行商问题dp[mask][i]表示已访问集合mask且当前在i看到题先看数据范围如果n只有20左右很可能能状压如果n在1000到100000之间先想线性DP或一维DP如果题目里反复出现“区间”“子串”“回文”这些词区间DP概率大如果明显有体积、重量、预算之类的限制就往背包DP靠。识别题型比直接动手写状态更重要方向错了后面全白费。5. 写DP的坑我替你先踩一遍5.1 索引和base case错位这是新手最容易踩的坑。我见过太多人把dp数组开成n结果转移时用到索引n就越界还有的题目字符串下标从0开始dp状态从1开始结果取字符时用了s[i]而不是s[i-1]整个答案全错。我的习惯是写代码前先把“dp下标含义”和“原始数据下标含义”写清楚比如dp[i]表示前i个元素原始数组用arr[i-1]。然后拿最小规模样例验证一遍比如n1、n2很快能发现下标问题。5.2 初始化没有区分“非法”和“合法”求最小值的问题如果dp数组初始化为0那所有本来不能达到的状态都会被0污染导致答案永远是0。比如编辑距离里dp[0][j]表示从空串变成某个串的编辑次数它必须初始化为jdp[i][0]初始化为i其他格子要初始化为一个很大的值。求最大值时又要区分“0”和“负无穷”。负无穷通常用float(-inf)或一个足够小的数比如-10**9。很多DP题目代码短问题就出在这几个初始值上调了一天以为算法错了其实只是初值没配对。5.3 状态定义维度不够有些题目的状态不是一维数组就能装完的。最典型的是股票交易问题你今天持有股票和没持有股票对明天的收益影响完全不同所以状态至少要加一维表示“是否持有”。另一个例子是最长递增子序列可以定义dp[i]表示“以第i个数结尾的最长递增子序列长度”这个定义自带“结尾”信息所以一维够用但如果只想用dp[i]表示前i个数的最长递增子序列长度会发现转移时根本不知道上一个数是多少反而更新不出来。状态定义不够后面怎么写都别扭所以宁可多花两分钟想清楚需要哪些维度也不要急着写循环。5.4 排查DP问题的通用方法最后分享一套我实际用了很久的排查流程。第一步找一组极小规模输入手工填一遍你设计的dp表看看每一步应该是什么再把你代码里的dp表打印出来对比这一步能解决八成问题。第二步检查转移方程里的下标和边界条件尤其注意j-weights[i]不要小于0i-1不要越界。第三步单独打印出base case那几行确认初始值符合预期。第四步如果答案还是不对把递归记忆化版本和DP版本同时跑一遍最小的随机样例用暴力搜索结果对比DP结果差距在哪里很快就能看出来。说实话动态规划的学习曲线比多数算法要陡但一旦你想明白“状态”和“转移”这两件事后面越写越顺。我个人还有一个习惯拿到题先在纸上写状态定义和转移方程再手算一遍小样例最后才开始打代码。面试中对着白板说状态定义其实也是在逼自己理清思路效果比直接闷头做题好很多。对我来说动态规划不是一套需要背的模板而是一种“把决策过程记录成表格”的思维方式想明白这件事一切就顺了。
阅读完成 · 觉得有帮助？
