你有没有发现“DP”这个词最近在热搜榜上同时养着两拨人。一拨人在搜算法题解、学动态规划另一拨人在找DP线材、看DisplayPort转Type-C的输出方案。巧了我在评论区还见过一个段子有人说自己学了三天DP到头来发现买的是根视频线。如果你搜DP是为了找线那现在可以退出去买线了如果你是想搞懂算法里的动态规划今天这篇应该能帮你把这条路走顺。动态规划Dynamic Programming几乎是算法面试里最绕不开的一块硬骨头也是很多人从“会写代码”到“会写算法”之间那道最明显的门槛。它既不像暴力搜索那样无脑也不像贪心那样看运气它是有一套完整方法论、但偏偏又最考验“设计感”的算法。我接触DP算起来也有七八年了从大学被背包问题折磨到怀疑人生到后来在竞赛里靠数位DP和区间DP拿分再到现在面试别人时看候选人怎么定义状态——这条路我踩过的坑应该值得你花点时间看看。1. 动态规划到底解决什么问题先把“动态”两个字忘掉1.1 一个被名字误导的算法我第一次接触动态规划的时候被“动态”这两个字带偏了很久。我以为它是一种在运行中不断调整策略的算法类似某种自适应控制、某种“动态”调整。事实证明完全不是那么回事。动态规划本质上一点都不“动态”。它的核心是一张表、一套递推关系、一组边界条件。你把这些东西定义好之后剩下的工作几乎是机械的、静态的。真正“动态”的只是你在脑子里设计状态转移方程那个过程。一旦方程写出来代码反而是所有算法里最好写的。很多人学DP觉得难难就难在它不像排序算法那样有个固定的代码模板。你背会快排就是快排背会归并就是归并。但DP没有万能模板它的模板是“方法论”怎么定义状态怎么写转移怎么定边界。这三个问题换一道题就是一个新解法所以很多人觉得DP像玄学实际上是你还没抓到那根主线。1.2 动态规划的两个底层前提重叠子问题和最优子结构在聊具体解法之前我先说两个几乎所有DP题都逃不开的前提理解了这两个东西你对DP的认知会清楚一大半。第一个叫重叠子问题。举个例子斐波那契数列你递归算F(10)你得先算F(9)和F(8)算F(9)你要算F(8)和F(7)。这个过程中F(8)被重复拆解了无数次。如果你用一个数组把每次算出来的结果存下来下次直接用这就是记忆化搜索也就是自顶向下的DP。如果你反过来从F(0)、F(1)一路递推到F(10)这就是自底向上的递推也就是我们最常见的DP写法。两条路本质相通。第二个叫最优子结构。意思是一个问题的最优解可以由它的子问题的最优解组合出来。比如你要算从第1层爬到第10层有多少种爬法每次爬1层或2层第10层的答案是第9层的答案加上第8层的答案因为最后一步要么从第9层跨1层过来要么从第8层跨2层过来。这背后就是最优子结构在起作用。1.3 用爬楼梯的例子把DP讲“破”说个谁都听过的例子爬楼梯。有n级台阶每次可以跨1级或2级问有多少种不同方式爬到顶。不用DP的写法是纯递归F(n) F(n-1) F(n-2)。看着简洁但你稍微算一下就会发现复杂度是O(2^n)n45的时候你电脑已经跑不动了。问题就出在大量重复计算上。用DP的思路你只要开一个数组dp让dp[0] 1站在地面算1种方式dp[1] 1一级台阶1种方式然后从2到n循环dp[i] dp[i-1] dp[i-2]。循环结束输出dp[n]。就这么简单。这个例子的价值是让你直观感受到DP就是把一个看起来需要递归拆到底的问题变成一张从前往后填的表。你不再重复计算任何东西每个子问题只算一遍。复杂度从指数级降到线性级这就是DP最原始、最核心的威力。注意很多教材喜欢把dp[0]定义为1理由是“原地不动是一种方案”。你如果不习惯也可以把dp[1]1、dp[2]2作为初始条件然后从3开始循环。两种做法都对关键是你自己心里要有一致性别混着用。2. 动态规划解题五步法从题意到递推式的最短路径2.1 五步法的具体拆解我自己带过不少新人发现大家面对DP题最大的困惑不是代码写不出来而是“不知道从哪开始想”。后来我把自己的思考过程总结成五步按顺序走一遍大部分中等难度的DP题都能解出来定义状态。用一个或多个维度描述“我已经处理到哪一步、当前处于什么情况”。这一步是DP的灵魂定义得好后面全是顺水推舟定义得差后面怎么调都是歪的。写出状态转移方程。搞清楚“当前状态能从哪些之前的状态转移过来”一般就是枚举最后一个动作。确定初始化。边界状态的值必须符合实际含义这一步错整张表都是错的。确定遍历顺序。要保证算dp[i]的时候它依赖的dp[j]都已经算过了。用小例子手动推演一遍。拿个n3或n4的小样例自己拿笔画一遍确认转移方程不会越界、不会漏情况。这五步里前四步是硬功夫第五步是大多数人偷懒跳过然后翻车的坑。你别嫌麻烦遇到新题先拿小数据手推比自己盲改代码快得多。2.2 一个完整的实战案例最长上升子序列LIS光说不练假把式拿一个面试高频题“最长上升子序列”看五步法怎么落地。题目是给定一个无序数组例如[10, 9, 2, 5, 3, 7, 101, 18]找出其中最长的严格上升子序列的长度。注意子序列不要求连续但相对顺序不能变。按五步走第一步定义状态。我选dp[i]表示“以第i个元素结尾的最长上升子序列长度”。这个定义很关键因为如果不要求“以第i个结尾”后面就很难写转移。第二步写转移方程。dp[i] max(dp[j] 1)其中0 j i且nums[j] nums[i]。意思是我把nums[i]接到某个比它小的数字后面长度就在那个数字的dp值基础上加1也可以不接任何人自己单独作为一个子序列所以dp[i]至少是1。第三步初始化。每个元素的dp值初始都是1因为每个元素自身就是一个长度为1的上升子序列。第四步遍历顺序。i从左到右j从0到i-1保证算dp[i]时所有dp[j]已知。第五步手推。数组[10, 9, 2, 5]dp[0]19比10小dp[1]12比谁都小dp[2]15前面比它小的只有2dp[3]dp[2]12。答案取max(dp)。逻辑没错。def 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)这个写法时间复杂度O(n^2)在n1000以内的题目完全够用。如果想更快可以再用一个数组维护“当前长度对应的最小结尾”配合二分查找把复杂度降到O(n log n)这个属于进阶优化后面会讲。2.3 为什么很多人学DP“一看就会一写就废”我见过太多人学DP的路径是看题解觉得秒懂关上题解写不出来再看题解恍然大悟上了考场还是不会。这不是你笨是学习方法出了问题。问题出在你看题解的时候跳过了最核心的“状态定义”环节直接看了答案。你记住了这道题的方程却没记住这道题是怎么想到这个状态、为什么这么定义。下次题目换个包装你就认不出来了。我的建议是刷DP题的时候先别看题解的前半部分只看题目逼自己想状态定义。想不出来可以看提示但看完提示一定要问自己一句为什么这个状态是对的它覆盖了所有可能在“最后一个动作”上发生的情况吗这才是把DP真正学进脑子里的方式。3. 五大经典DP模型拆解背包、序列、区间、数位、状压树形3.1 背包问题01背包与完全背包背包问题绝对是DP里的第一大门派面试八股和竞赛入门都绕不开。01背包的问题描述是有n件物品每件物品有重量w[i]和价值v[i]背包容量是C问能装下的最大价值是多少。每件物品最多选一次。标准状态定义是dp[i][j]表示“从前i件物品中选总重量不超过j时的最大价值”。转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。意思就是面对第i件物品要么不装要么装。如果装那之前i-1件物品只能用掉j-w[i]的容量。这里有一个非常经典、也是面试官最爱问的细节用滚动数组优化成一维dp[j]时j要倒着遍历。为什么因为一维数组里dp[j-w[i]]必须是“上一轮、还没被本轮更新过”的值如果j从小到大遍历dp[j-w[i]]可能已经被本轮前面的循环覆盖成新值了那你就等于允许了一件物品被选多次01背包就退化成完全背包了。倒着遍历则保证dp[j-w[i]]还是旧的。# 01背包一维滚动数组容量j倒序遍历 for i in range(n): for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])而完全背包每件物品可以选无限次恰好相反j要正序遍历这样dp[j-w[i]]会被本轮更新覆盖天然实现了“可以重复选”。两个背包唯一的区别就在这一行遍历顺序上很多人笔试时一紧张就写反这里一定要刻进DNA。3.2 序列类DP最长公共子序列与编辑距离序列类DP的套路是“两个序列就开二维表”。最长公共子序列LCSdp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。转移分两种情况如果A[i-1]等于B[j-1]那么dp[i][j] dp[i-1][j-1] 1如果不相等dp[i][j] max(dp[i-1][j], dp[i][j-1])。还有一种更进阶的序列DP是编辑距离就是算把一个字符串变成另一个字符串最少需要多少次操作增、删、改各算一次。dp[i][j]仍然表示A的前i个字符变成B的前j个字符的最小代价。转移方程稍微复杂一点点if a[i - 1] b[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j] 1, # 删除a[i] dp[i][j - 1] 1, # 在a中插入b[j] dp[i - 1][j - 1] 1) # 把a[i]替换成b[j]这类题目最容易错的地方是初始化。dp[0][j]必须等于j因为空字符串要变成B的前j个字符只能靠插入j次dp[i][0]必须等于i因为A的前i个字符要变成空串只能靠删除i次。这个初始化的意义在于它给整张表的边界铺好了地基地基歪了后面全歪。3.3 区间DP合并石子与矩阵链乘区间DP是另一种经典模型特征是“在一个区间上进行合并或划分”。最典型的例子是石子合并有几堆石子排成一排每次只能合并相邻两堆代价是两堆石子的重量之和问把所有石子合并成一堆的最小总代价。状态定义是dp[i][j]表示合并从i到j这一整段石子的最小代价。转移时枚举一个分割点k把区间[i,j]分成[i,k]和[k1,j]两段分别合并后再把两堆合成一堆代价加上这段的总重量dp[i][j] min(dp[i][k] dp[k1][j] sum(i,j))其中k从i到j-1。区间DP有个特别的遍历顺序不是从1到n从外到内而是按区间长度从小到大去填表。先算长度为1的不用合并代价是0再算长度为2的、3的……一直到整个区间。顺序错了你会发现自己算一个长区间时依赖的短区间还没填好。这类题容易踩的坑是状态定义里漏掉“相邻”这个条件。有些DP题是允许从任意堆之间合并的那用贪心或者堆就能解一旦要求只能合并相邻就必须用区间DP。看到“相邻”两个字优先往区间DP上想。3.4 数位DP统计问题的高效解法数位DP是很多人觉得“太玄”的一类题但它的本质其实就是DFS加记忆化。它解决的问题长这样给定一个区间[L, R]统计这个区间内满足某个条件的数的个数。比如“数字中不含4”“数字中连续两位不能是……”。套路是先把区间查询转化成F(R) - F(L-1)的形式然后写一个dfs(pos, status, limit)。pos表示当前处理到第几位status表示当前已经携带的信息比如上一位数字是几、当前是否已经进入了合法状态limit表示当前位是否被上限数字约束。如果limit为False意味着这一位可以随便填0到9那么后面所有情况的数量是固定的可以直接用记忆化缓存。# 数位DP的通用框架伪代码 def dfs(pos, status, limit): if pos n: return 1 if is_valid(status) else 0 if not limit and memo[pos][status] ! -1: return memo[pos][status] up digits[pos] if limit else 9 ans 0 for d in range(0, up 1): ans dfs(pos 1, new_status(status, d), limit and d up) if not limit: memo[pos][status] ans return ans很多新手第一次看数位DP会问为什么要limit这个参数因为上限数字的约束是动态的。比如统计[1, 321]时如果百位取了2那十位最大可以到9如果百位取了3那十位最大只能是2。limit就是用来标记“当前这位有没有被上限压着”的。数位DP的难点在于status的设计它高度依赖题目条件。这部分没有太多模板可套需要多刷几道题积累手感。但框架是固定的你把这个dfs模板背熟遇到统计数字个数的题至少有一个下手方向。3.5 状态压缩DP与树形DP进阶必备状态压缩DP简单说就是把一个集合的取舍状态用一个整数的二进制位来表示。最经典的例子是旅行商问题TSP有n个城市两两之间有距离问从起点出发走完所有城市再回来最短路径是多少。dp[mask][i]表示“已经访问过的城市集合是mask当前停留在城市i”的最短路径长度。mask是一个整数它的第k位是1代表第k个城市已经访问过了。转移就是枚举下一个要去的城市jdp[mask | (1 j)][j] min(dp[mask][i] dist[i][j])。状态压缩DP的数据范围一般很小n通常在20以内因为2^20大约是一百万再大就存不下了。树形DP则是把DP建立在树的遍历上特征是要算“根节点的答案”得先知道“所有子节点的答案”所以一般用DFS后序遍历。经典题是“没有上司的舞会”每个员工有快乐值如果选了这个人他的直接下属就不能选如果不选他下属可选可不选。需要dp[node][0]和dp[node][1]两个状态分别表示以node为根的子树里不选/选node能获得的最大快乐值。树形DP写起来套路感很强本质上就是DFS里做一次聚合。我第一次写树形DP的时候觉得它像“在树上跑一个后序的01背包”这个类比一直用到现在还是很贴切。4. 区分DP和贪心、分治、递归别再傻傻分不清4.1 四张脸谱放在一起对比我经常在面试里问候选人贪心和DP都能求最优解区别在哪好多人答不上来。我后来习惯用一张表把四个“长得像”的算法分开算法核心思想子问题关系典型代表分治大问题拆成互不相干的子问题子问题独立、不重叠归并排序、快速排序DP大问题拆成重叠的子问题记录子问题答案子问题高度重叠背包、LCS贪心每一步选局部最优不做回溯不要求子问题靠数学证明活动安排、哈夫曼编码递归一种实现方式不是算法可以是分治也可以是DP的实现手段DFS、回溯分治和DP最本质的区别就是子问题重不重叠。归并排序的左半部分和右半部分完全不相干各排各的而斐波那契的F(8)是F(9)、F(10)重叠依赖的。所以归并排序不需要记忆化DP必须记忆化。4.2 怎么判断一道题该用DP还是贪心判断标准就一个词后效性。简单说就是你这一步的选择会不会影响后续可选的决策空间如果不会贪心大概率够用如果会影响请老老实实上DP。举两个对比鲜明的例子。“跳跃游戏2”给定数组每个元素代表你在该位置最多能跳多远求用最少步数跳到最后一个位置。这题的标准解法是贪心因为你在当前位置选择“跳到下一个能跳更远的点”这个决策并不会毁掉未来的选择空间每步都是当前最优。但如果加一个限制比如不同位置有不同的跳转花费那贪心就废了必须DP。4.3 无后效性DP状态设计的“上帝视角”DP为什么能保证全局最优靠的就是无后效性也叫马尔可夫性——某个阶段一旦确定之后的发展不受这个阶段之前各阶段的影响。翻译成人话就是dp[i]一旦算出来后面要用它的时候你完全不需要关心dp[i]是怎么算出来的只需要用它的值。这个性质对状态设计有很强的指导意义。你定义状态时必须保证当前状态已经“封存”了所有将来需要的信息。如果算完dp[i]之后后面还需要知道“i之前某个具体选择了什么”那说明你的状态定义漏信息了要额外加维度。5. DP超时超内存怎么办四大优化套路盘点5.1 滚动数组空间不够的救法很多DP方程里dp[i]只依赖dp[i-1]或者dp[i-1]和dp[i-2]那就不需要保留整个二维数组只要开两行或者几个变量滚动使用。斐波那契数列就是最极端的例子全程只需要两个变量不需要数组。a, b 0, 1 for _ in range(n): a, b b, a b区间DP里也经常用滚动不过要注意如果状态依赖的是整个dp[i][k]的一部分比如依赖同行的多个位置滚动数组就需要小心覆盖顺序。安全起见先确认依赖关系再决定滚动方向。5.2 状态压缩二维压一维这个在01背包里已经提过了。二维dp[i][j]压成一维dp[j]关键在于遍历顺序和原始二维表保持语义一致。这类优化不仅省空间写起来也更快是实战中最常用的优化手段。再补充一个例子LCS的滚动数组。LCS其实只需要上一行的信息所以可以用dp[2][j]交替存储空间从O(n*m)降到O(m)。竞赛里如果题目数据范围大得离谱这个优化经常能救你一命。5.3 二分优化与数据结构优化LIS可以用贪心加二分做到O(n log n)。思路是维护一个数组tailstails[len]表示长度为len的上升子序列的最小结尾值。遍历原数组时用二分在tails里找到第一个大于等于当前元素的位置替换它。这个技巧学起来简单但你要是不提前了解很难在考场上自己想到。另一个常见优化是用树状数组或线段树加速转移。比如二维DP里面有一个max操作而且转移来源是一段连续区间的最值那就可以用数据结构维护区间最值把O(n)的转移降到O(log n)。这种优化在竞赛里尤其常见面试里一般考察得少但属于“知道有这个东西”能加分的范畴。5.4 斜率优化与四边形不等式慎入这两个优化是竞赛向的内容但既然聊到优化套路我还是把名字报出来。斜率优化用于转移方程里出现i和j的乘积项比如dp[i] min(dp[j] a[i]*b[j])这时候可以用单调队列维护一个凸包把复杂度降一维。四边形不等式用于区间DP里状态转移具有单调性的情况可以优化掉一维枚举。我不是劝所有人都去学这两个东西。如果你只准备面试完全没必要碰如果打竞赛等前面那些基础优化都熟练了再学也不迟。我当年花了整整一周才把斜率优化啃明白说实话性价比不高除非你的目标赛事真的会出这类题。6. 新手最常见的6个DP错误与调试心法6.1 六大致命错误速查我这些年帮人改过的DP代码90%都栽在下面这六个问题上第一个数组越界。循环里没处理好边界条件访问了dp[-1]或dp[n]的位置。Python里dp[-1]不会立刻报错它会默默取最后一个元素这种错误特别阴险不打印中间结果根本发现不了。第二个初始化错误。最常见的是把dp所有值初始化为0但题目需要求最小值正确的初始值应该是正无穷大。你初始化错了算出来的最大值永远是0而不是真实答案。第三个遍历顺序错误。该倒序的时候正序该按长度从小到大却按位置顺序。这个问题在背包和区间DP里最频发。第四个状态定义含糊。用一个维度描述了两件事导致转移时无法判断当前状态到底属于哪种情况。这种错误不会崩溃只会让你的答案莫名其妙地偏小或偏大。第五个溢出问题。C选手的低级失误。DP数组开int中间计算却可能超过2^31必须改用long long。Python虽然不用考虑这个但如果你做的是C算法题这是实打实的坑。第六个忽略边界特判。比如数组长度为0、n等于1这种边界情况经常导致dp数组太小循环直接越界。6.2 调试DP的方法论打印、对拍、手推DP出错了怎么排查我有一套固定的流程你照着来基本能秒杀90%的问题。第一步打印整张dp表。把每个状态的最终值都打出来拿一个特别小的样例人肉对照手推的结果。这一步能发现绝大多数“状态转移逻辑错误”。我最常做的事就是print(dp)然后盯着表格看三分钟立刻就能定位到第一个开始不对的位置再顺着那个位置往前推问题就出来了。第二步如果是逻辑实在对不上回到状态定义重新审视别在转移方程上硬调。很多人喜欢拿着一个方程反复试不同的初始值越试越乱。正确的做法是回到五步法的第一步先问自己dp[i][j]到底代表什么意思这个定义能覆盖所有可能的情况吗第三步对拍。拿你的DP版本和一个暴力搜索版本一起跑随机小数据比较结果。暴力算法不用管效率只要正确就行数据范围控制在n 10跑几百组随机用例能帮你验证绝大多数的边界情况。我在竞赛里基本人手一套对拍器没有它我很多DP题根本不敢交。6.3 用三个问题给DP做“术后复盘”最后分享一个我每次刷完一道DP题都会问自己的复盘模板就三个问题第一这道题的状态定义能不能换一种两种定义优劣在哪这个问题能帮你拓宽“设计状态”的视野。第二转移方程如果漏掉某一条路径会怎样这个思考能帮你检查状态覆盖的完备性。第三这个题的模型还能套到哪些变体上比如01背包能套在“选或不选”的决策问题上LIS能套在“求最长递增序列”的各种变体上。总结模型比刷题数量更重要。6.4 日常训练安排建议很多人学DP脑子里没节奏感今天看背包明天看数位后天又回头做LIS知识碎片化严重。我建议按专题刷一个专题至少刷到稳定AC 15到20题再换每个专题刷完必须亲手整理一页自己的“状态定义笔记”。刷完一个专题得能画出这个专题所有变体的关系图才算过关。我个人在实际操作中的体会是DP是最讲究“时机”的算法你状态定义得好转移方程几乎是“倒出来”的定义得不好后面用再多的优化技巧都像在救一个方向错误的项目。与其急于优化、急于背模板不如先把每个经典模型的“状态定义为什么这么设计”想透彻。等你刷到一定量之后你会突然发现DP题其实就那几种套路换汤不换药那一刻你就真的入门了。