动态规划DP这个东西很多人在初学算法时都听过它的大名然后被“状态转移方程”这五个字劝退。我当年也是第一次看01背包问题的解法盯着那两行循环看了整整一个下午想不明白为什么一个二维数组倒过来遍历就能算出最优解。后来刷了上百道DP题、在工程里又用DP解决过几次实际需求之后才慢慢摸清楚这套方法论的门道。用一句话概括动态规划就是“把一个大问题拆成若干有依赖关系的小问题用表格把每个小问题的答案记下来避免重复计算”。它不是什么高深莫测的魔法本质就是“递归 备忘录”的递推版本只不过写法从函数调用变成了填表。这篇文章我打算把动态规划的完整套路拆开揉碎讲一遍从核心原理到常见题型从手写推导到性能优化再到调试技巧一次性讲透。适合刚接触DP的初学者也适合刷题刷到瓶颈、想系统梳理一遍的中级选手。1. 动态规划的核心思想与解题框架很多教程上来就抛状态转移方程搞得跟天书一样。其实DP的思维方式很简单你只需要回答三个问题这个问题能不能拆拆完之后小问题之间有没有重复能不能用表格把重复结果存下来1.1 最优子结构与重叠子问题DP的两个判断标准先说说什么样的题目适合用动态规划。我用一个最经典的上楼梯例子解释假设你要爬10级台阶每次可以走1级或2级问有多少种不同的走法。这个问题可以这样拆到第10级的走法 到第9级的走法 到第8级的走法。因为最后一步要么从第9级跨1级上来要么从第8级跨2级上来。这里就出现了第一个关键特征——最优子结构大问题的最优解可以由子问题的最优解推导出来。第10级的答案只取决于第9级和第8级的答案子问题之间是独立的。再往下拆你会发现计算第9级需要第8级和第7级计算第8级也需要第7级和第6级第7级被重复计算了。这就是第二个关键特征——重叠子问题同一个子问题会被多次使用。如果直接写递归时间复杂度是O(2^n)指数爆炸但如果用一个数组把每级台阶的答案存下来每个子问题只算一次时间复杂度就降到了O(n)。所以判断一道题能不能用DP就抓这两个标准能不能拆、拆完有没有重复。两者都有DP基本就是最优解只有前者没有后者用分治比如归并排序更合适都没有那多半是贪心或者模拟的范畴。1.2 状态、转移、边界DP三要素到底在说什么搞懂了适用条件接下来就是DP的核心框架了——三要素状态定义、状态转移方程、初始化和边界条件。这三件事对应到代码里就是dp数组怎么开、循环体怎么填、dp[0]是多少。状态定义是最关键的。你定义的dp[i]或者dp[i][j]到底表示什么含义决定了整个题目的难度。同样是上楼梯你可以定义dp[i]为“到第i级台阶的走法总数”也可以定义成“到第i级台阶最少需要几步”后者就是另一个问题了。状态定义得好转移方程呼之欲出定义得差后面全卡住。状态转移方程是整个DP的“物理规律”它描述了状态之间的递推关系。还是以上楼梯为例dp[i] dp[i-1] dp[i-2]。这个式子不是凭空来的它的推导逻辑是“最后一步怎么走的”——这是我在做线性DP时最常用的思考方式不要从起点往后想而是站到终点往前想看看最后一步有几种可能。初始化和边界条件是新手最容易翻车的地方。dp[0]到底是0还是1循环从1开始还是从2开始数组要开多大这些细节每个题目都不一样需要具体分析。我的建议是写代码之前先用纸笔把前3到5个数手推一遍确认边界条件合理再动手写代码。省下来的调试时间绝对不止写的那几分钟。2. 五类高频DP场景与套路拆解动态规划不是一锅粥它内部有清晰的分类。不同分类对应不同的状态定义套路和转移思路掌握分类相当于拿到了题库的“目录”。2.1 线性DP一维数组走天下线性DP是最基础的一类特征是状态只沿着一个维度推进。典型题目有斐波那契数列、最长递增子序列LIS、最大子数组和等。以最长递增子序列为例给定数组[10, 9, 2, 5, 3, 7, 101, 18]要求找出最长的严格递增子序列长度注意子序列可以不连续。状态定义dp[i]表示“以第i个元素结尾的最长递增子序列长度”。转移时遍历i之前的所有元素j如果nums[j] nums[i]说明nums[i]可以接在以nums[j]结尾的子序列后面那么dp[i] max(dp[i], dp[j] 1)。核心代码如下def length_of_lis(nums): if not nums: return 0 n len(nums) dp [1] * n # 每个元素至少自己是一个长度为1的子序列 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)这段代码虽然简单但它包含了线性DP的所有要点一维数组、双层循环、O(n^2)时间复杂度。注意dp数组初始值设为1因为每个元素单独就是一个长度为1的递增子序列这个初始化很关键。2.2 背包DP从01背包到完全背包的进阶之路背包问题是DP里最经典的模型没有之一。01背包的题干是这样的有N件物品和一个容量为V的背包第i件物品的重量是w[i]价值是v[i]每件物品最多拿一次问能装下的最大价值是多少。状态定义dp[i][j]表示“前i件物品中在背包容量为j时能获得的最大价值”。转移时面对第i件物品只有两种选择不拿那么dp[i][j] dp[i-1][j]拿那么dp[i][j] dp[i-1][j-w[i]] v[i]前提是j w[i]。两者取最大值dp [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): for j in range(1, V 1): if j w[i]: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) else: dp[i][j] dp[i-1][j]这里有一个可以优化的点观察转移方程dp[i][...]只依赖于dp[i-1][...]也就是上一行的数据。所以我们可以把二维数组压缩成一维但必须注意遍历顺序——容量j要从大到小遍历。为什么因为一维数组里dp[j]在更新时可能已经被“本轮”的数据污染了。如果从小到大遍历dp[j-w[i]]可能已经被本轮更新过了相当于一件物品被拿了多次那就变成完全背包了。从大到小遍历可以保证dp[j-w[i]]还是上一轮也就是还没拿当前物品的数据这正是01背包想要的效果dp [0] * (V 1) for i in range(1, N 1): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])这个“为什么倒序”的问题十个学DP的人里八个被卡过。我当年也是死记硬背“倒序遍历”直到有一天自己画了一遍状态转移的表才彻底明白。所以建议你也亲自画一遍把dp数组在每一轮循环之后的值打印出来看一维数组的覆盖过程比看十遍博客都有效。2.3 区间DP先处理小区间再合并大区间区间DP解决的是“在一个区间上进行决策”的问题典型代表是石子合并、矩阵链乘法。这类题的状态定义通常是dp[i][j]表示“区间[i, j]上的最优解”转移时在区间内枚举分割点k把大区间拆成两个小区间求解。以石子合并为例有N堆石子排成一排每堆重量已知每次只能合并相邻两堆花费为两堆重量之和问把所有石子合并成一堆的最小总花费。状态转移方程是dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j)) # k从i到j-1实现时注意循环顺序区间长度从小到大。先算长度为2的所有区间再算长度为3的这样保证计算较长区间时它依赖的较短的子区间已经被算过了for length in range(2, N 1): for i in range(N - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] prefix[j1] - prefix[i])区间DP的套路感很强状态定义好之后剩下就是三重循环的模板操作难点往往在于状态转移方程的设计——尤其是“合并操作”的代价怎么计算。2.4 数位DP按位枚举的计数高手数位DP解决的是“在某个范围内满足某种数字特征的数有多少个”这类问题。比如统计1到N之间不含4的数字个数、数字中0的个数等于1的个数等。这类题的典型套路是“记忆化搜索”而非传统的递推填表。状态一般包含三个维度当前处理到第几位、当前是否处于“紧贴上限”的状态、前面已经积累了什么样的特征值用个位、十位等做维度。以统计数字中不含4的数量为例核心思路是把数字N拆成每一位从高位到低位DFS枚举每个位置可选的数字范围受上限约束如果之前都紧贴上限当前位就不能超过N的对应位。模板如下def count_numbers(n): digits list(map(int, str(n))) from functools import lru_cache lru_cache(None) def dfs(pos, tight): if pos len(digits): return 1 limit digits[pos] if tight else 9 res 0 for d in range(limit 1): if d 4: continue res dfs(pos 1, tight and d limit) return res return dfs(0, True)数位DP的难点在于状态设计。很多题目会在记忆化搜索的参数里加很多维度比如“前导零”“是否已出现某数字”“当前数对某个数的余数”等。我的建议是不要试图背模板而是先想清楚“什么信息会在后续枚举中影响结果”只有影响结果的才需要放进状态参数里。2.5 状态压缩DP当维度爆炸时的终极方案状态压缩DP也称“状压DP”适用于状态只有“选/不选”两种可能、而元素数量不大一般n ≤ 20的问题典型代表是旅行商问题TSP、铺地砖问题。它的核心思想是把一组布尔状态压缩成一个整数的二进制位用这个整数作为dp数组的下标。以TSP简化版为例n个城市从0出发每个城市恰好访问一次最后回到0求最短路径。状态dp[mask][i]表示“已访问城市集合为mask当前在i城市”的最短距离。mask是一个整数它的第k位是1表示第k个城市已被访问。转移时枚举下一个未访问的城市jdp [[inf] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0出发mask只有第0位为1 for mask in range(1 n): for i in range(n): if not (mask i) 1: continue for j in range(n): if (mask j) 1: continue new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j])状压DP的代码写起来不算难但空间复杂度是O(2^n * n)当n超过20时基本就跑不动了这是它最大的局限。同时也要提醒一句状态压缩不是一种“高级炫技”而是当状态无法用一两个整数维度表示时用二进制位做状态编码的自然延伸。很多用状压DP的题目换成多维数组也能做只是维度太多写起来痛苦。3. 完整推导一道DP题从暴力递归到空间优化拆概念讲套路总归是纸上谈兵这一章我拿一道典型题目——最长公共子序列LCS带你完整走一遍DP的四个实现阶段暴力递归、记忆化搜索、递推DP、空间优化。这道题是面试高频题也是理解DP演进路径的最佳样本。3.1 题目定义与状态设计给定两个字符串text1 abcde 和 text2 ace求它们的最长公共子序列长度。这里的“子序列”指的是原字符串中按顺序出现但不一定连续的字符序列ace就是abcde的子序列最长公共子序列长度为3。直接想暴力做法可以枚举text1的所有子序列去检查它是不是text2的子序列时间复杂度是O(2^m)指数级。但暴力递归可以换一种更聪明的“指针移动法”。定义递归函数f(i, j)表示“text1从第i个位置开始、text2从第j个位置开始的最长公共子序列长度”。那么分两种情况如果text1[i] text2[j]当前这个字符一定可以选进公共子序列所以f(i, j) 1 f(i1, j1)。如果text1[i] ! text2[j]则要么跳过text1[i]要么跳过text2[j]取两者较大值f(i, j) max(f(i1, j), f(i, j1))。这就是最原始的“状态转移方程原型”。暴力递归就是直接按这个公式写代码但显然会有大量重复计算——f(1,1)可能被f(0,1)和f(1,0)都调用。于是我们有了记忆化搜索。3.2 记忆化搜索与递推DP的实现对比记忆化搜索就是在递归函数外面套一个缓存表计算过的f(i,j)直接存起来下次直接查表def lcs_memo(text1, text2): m, n len(text1), len(text2) memo [[-1] * n for _ in range(m)] def dfs(i, j): if i m or j n: return 0 if memo[i][j] ! -1: return memo[i][j] if text1[i] text2[j]: memo[i][j] 1 dfs(i 1, j 1) else: memo[i][j] max(dfs(i 1, j), dfs(i, j 1)) return memo[i][j] return dfs(0, 0)这里memo[i][j]初始化为-1用来判断是否已经计算过。注意边界条件是i或j走到字符串末尾返回0。记忆化搜索的逻辑非常接近我们人脑的思考方式写起来不容易错。但它的缺点是递归有调用栈开销在某些语言里还可能栈溢出。于是更常见的做法是把递归改写为递推填表。把递归的返回值理解成dp[i][j]——text1前i个字符和text2前j个字符的LCS长度递推公式和递归一样但循环顺序是从小到大def lcs_dp(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]注意这里dp数组的大小是(m1) × (n1)多出的一行一列是空串的边界dp[0][j]和dp[i][0]都是0表示如果有一个字符串是空的公共子序列长度自然是0。3.3 滚动数组优化把二维压成一维观察转移方程dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1]也就是当前行只依赖上一行和当前行的左侧。这意味着我们不需要保留整个二维表用两个一维数组甚至一个一维数组就够了。用两个一维数组的写法prev记录上一行cur记录当前行每更新完一行就交换。用一维数组的写法稍微tricky一点因为dp[j]同时充当了“上一行的值”和“当前行的值”需要一个变量暂存左上角的值def lcs_optimized(text1, text2): m, n len(text1), len(text2) if m n: return lcs_optimized(text2, text1) # 空间优化技巧让短字符串做列 dp [0] * (n 1) for i in range(1, m 1): prev 0 # 代表 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 保存当前dp[j]即dp[i-1][j]下一轮用 if text1[i - 1] text2[j - 1]: dp[j] prev 1 else: dp[j] max(dp[j], dp[j - 1]) prev temp return dp[n]顺手还能做一个工程优化判断两个字符串的长度让较短的字符串作为列进一步降低空间占用。这类“让维度变小”的优化思路在真实的算法面试中很加分因为面试官不仅看你会不会做还看你会不会优化。我个人的经验是做DP题优先写二维递推版本先保证正确再考虑空间优化。一上来就写滚动数组很容易把自己绕晕特别是需要依赖左上角值的时候。4. 性能优化与工程落地的实战心得算法题里的DP和真实业务里的DP侧重点不一样。竞赛里追求的是极致的时间和空间复杂度工程里更看重代码的可读性、可维护性和边界情况的鲁棒性。这一章我结合自己的实际经验聊聊DP从“会写”到“用得好”的几个关键问题。4.1 复杂度计算你的DP能跑过数据范围吗拿到一道DP题先看数据范围再决定怎么实现。这一步能帮你提前过滤掉很多错误的方案。时间复杂度的计算很简单状态数量乘以每个状态的转移代价。比如前面LCS的二维DP状态有m×n个每个状态O(1)转移总复杂度O(m×n)。01背包的N件物品×容量V状态数N×V每个状态O(1)转移复杂度O(N×V)。但有个坑容易被忽略很多DP的状态转移不是O(1)的。比如最长递增子序列的朴素DP每个状态要遍历所有之前的元素转移代价是O(n)所以总复杂度是O(n^2)。区间DP里枚举分割点k也是类似总复杂度是O(n^3)。这类“多一重循环”的复杂度经常被人漏算导致估算严重偏差。我的建议是写代码之前先算一遍状态数和转移代价心里有数这题的极限数据规模是多少。比如O(n^2)的算法n到5000就可能需要25×10^6次运算在Python里已经有点吃力了如果n是10^5就必须换思路。空间复杂度同理。二维数组dp[10001][10001]光是开数组就是1亿个整数在大部分语言里直接爆内存。这时候要么用滚动数组把空间压下去要么考虑状态压缩要么就得重新设计状态。数据范围是DP方案选型的首要参考指标。4.2 DP的调试黑科技打印DP表很多人在DP写错的时候改了半天都不知道问题出在哪。我调试DP题最常用的方法就是把dp表打印出来。别笑这招真的能救命。当你的结果不对先把dp数组的前几行前几列打印出来和手推的预期值对比就能很快定位是初始化错了、转移方程写错了还是循环边界写错了。举个例子我调过一道矩阵链乘法的DP按区间长度从小到大填表结果算出来的值明显偏大。打印dp表之后发现循环边界里j写成了n而不是ilength-1导致数组访问越界越到了下一行后面的值全被污染了。这种错误光靠看代码很难发现但打印表格一眼就能看到数值不合理的行。调试时还有一个技巧对于小数据可以和暴力解法对拍。写一个递归或枚举的暴力版本随机生成小规模数据把DP结果和暴力结果对比。这个习惯我从刷题保持到工作中写任何动态规划模块先用小规模数据跑通对拍再扩大数据量能省掉无数线上排查的时间。4.3 DP在真实业务中的典型使用场景说完理论说说DP在工程里真正用得上的地方。很多人在公司写业务代码觉得算法题和日常工作关系不大其实DP在不少领域都是刚需。比如文本编辑距离也就是Levenshtein Distance它本身就是一组二维DP现在各类代码编辑器里的拼写检查、diff算法、语音识别的文本对齐都用到了类似方法。再比如资源分配问题——把一个预算分配给多个部门每个部门投入不同的金额获得不同的收益怎么分配收益最大这就是多重背包的变体。还有路径规划地图导航中最短路径算法虽然有专门的Dijkstra、A*但某些特定约束下也会退化成DP问题例如车辆行驶中的能耗最优规划。我之前做过一个项目管理系统的排期模块需要在多个任务中选择子集在给定时间内完成每个任务有预估工时和收益目标是在总工时不超过上限的情况下让收益最大化。这不就是妥妥的01背包吗把工时当重量、收益当价值容量是总工时预算跑一遍背包DP就搞定了。当时同事看到代码里只有一个一维数组倒序遍历问我这是啥黑魔法我给他讲了十分钟01背包的原理。所以别觉得算法题在工程里没用只是你没遇到用得上它的场景而已。另外一个建议是能用现成库或算法的时候不要重复造轮子。比如编辑距离很多语言标准库或第三方库已经实现了直接调库更稳妥。但在没有现成库、或者需要定制状态转换规则的时候亲手写DP反而是唯一可行的方案。写的时候注意把状态定义、初始化、转移方程用注释写清楚不然下一个人看你的dp数组跟看天书一样。5. 常见问题与避坑指南DP刷多了你会发现容易错的永远是那么几个地方。我把这几年刷题和面试中反复被踩的坑整理成了一张速查表写代码之前扫一眼能减少一大半的“低级错误”。5.1 高频报错边界条件与数组初始化常见错误现象原因与解决方法dp数组大小开错数组越界dp大小一般是长度1因为要多留一个空串的边界位置忘记初始化dp[0]结果偏大或偏小每个题目都要单独分析初始值不能套模板循环边界多1/少1漏算最后一个元素或访问未初始化区域写循环时把i0和in两个极端情况手推一遍二维数组行列搞反结果异常用dp[i][j]时先弄清楚i和j分别代表什么别在循环里搞混变量命名不清改来改去自己都乱了dp、w、v这种缩写要固定含义或直接使用语义化命名我的经验是90%的DP bug出在“差一错误”off-by-one上。因为dp数组通常多开了一位用于边界遍历时从1开始还是从0开始结束条件是小于n还是小于等于n这些细节稍微分神就会写错。最有效的规避办法是写完代码后用一个长度为1或2的极小测试用例手动跑一遍循环把每一步的i、j、dp值写下来和预期对比。5.2 逻辑陷阱别把贪心套进DP的壳区分贪心和DP是一个高频考点也是一堆人的知识盲区。简单说贪心是每一步都选当前看起来最优的不做回头调整DP是穷举所有可能用查表避免重复计算。贪心快但可能得到局部最优DP慢但保证全局最优。经典对比是“找零钱”问题假设有1元、5元、11元三种面额要找15元。贪心会优先用大的先拿11元剩下4元只能全用1元一共5张。但最优解是3张5元只有3张。贪心在这一题挂了因为局部最优先用最大面额没有带来全局最优。而DP会枚举所有组合找到真正的最少张数。这个对比在面试里非常常见面试官就是想看你能不能准确判断一个题目该用贪心还是DP。我的判断方法是如果“当前这一步的最优选择”会影响未来的可选范围并且未来的选择又会影响最终结果那大概率需要用DP如果每一步的选择互不影响、局部最优就能拼出全局最优才可以用贪心。5.3 记忆化搜索还是递推到底选哪个这两种写法本质上是同一种思路的两个方向记忆化搜索是自顶向下从大问题出发递归到小问题递推是自底向上从小问题出发迭代到大问题。两者时间复杂度没有本质区别但在不同场景各有优劣。记忆化搜索的优势是代码逻辑贴近人的思维状态定义想清楚了几乎不会写错而且天然避免了计算“用不到”的状态——递推可能会填一整张表但记忆化只算真正需要的格子。缺点是递归有系统栈开销极端数据下可能栈溢出。递推DP的优势是性能稳定、无栈溢出风险而且可以方便地用滚动数组优化空间。但它的代码顺序必须严格按照状态依赖关系来循环的顺序错了就是致命错误。我的选择标准是面试写题优先递推DP因为它更直观、更容易和面试官讨论复杂度遇到状态维度多、转移顺序不好确定的题改用记忆化搜索先保证正确性。实际工作中如果只是需要算一次结果哪个写着顺手用哪个但如果在一个高QPS的服务里跑那必须递推空间优化递归的调用栈开销在热路径上完全不可接受。6. 写在最后的一点刷题建议刷DP题最忌讳的是“看题—看答案—背代码—下一题”这样刷100题也建立不了自己的解题框架。我比较推荐的方式是“四步法”拿到题目先把暴力递归写出来哪怕复杂度再高也没关系然后加上备忘录变成记忆化搜索再把递归改成递推填表最后分析能否空间优化。这四步走完你对一道题的理解会深刻得多。我见过太多人一上来就想着怎么优化结果状态都定义错折腾半天还写不出来。先保证正确再追求高效。一道DP题能写出正确的O(n^2)解答已经超越了很多人在这个基础上再去想O(n)的优化才有意义。另外DP的题感需要靠量大来堆。我当年学DP的时候连续两周每天做5道以上的DP题从斐波那契、爬楼梯、打家劫舍这些入门题做起慢慢过渡到01背包、LCS、编辑距离、区间DP。两周之后再看到新题目第一反应就不再是恐惧而是条件反射地开始想“状态怎么定义、转移方程长什么样”——这种思维惯性就是刷出来的。动态规划的坑很多但它的正反馈也来得很快。一旦你掌握了“状态 转移 边界”这套思考方式再看各种变体题会发现万变不离其宗。希望这篇文章能帮你跨过那道坎。