★ FEATURED ARTICLE 动态规划这块我在刷题初期吃了不少亏。尤其是dp数组一开始总觉得定义出来了、转移方程写出来了代码跑通就算会了。结果过两周再遇同类题还是不会。后来我慢慢梳理出了一套dp数组的“套路化”理解方式现在看到很多题其实都能套进同一个框架里去想。这篇就来聊聊我总结的这套方法重点用01背包问题做例子拆开讲因为它是理解dp数组设计逻辑最好的切口之一。无论你是刚接触动态规划的新手还是刷了一两百道题但总觉得没摸到门道的人这篇文章都会有点用。我会把“为什么这么定义”“为什么这么初始化”“为什么这么遍历”这些文档里不会细讲的东西用大白话拆透。1. 动态规划的思维起点你其实一直在用枚举动态规划听起来高深但它的起点很朴素穷举。任何动态规划问题理论上都能用暴力递归枚举所有可能只是直接枚举往往是指数级复杂度跑不动。1.1 暴力递归为什么会慢拿最简单的斐波那契数列来说f(n) f(n-1) f(n-2)你写成递归每一层都会分裂出两个分支。算f(45)的时候整个调用树会膨胀到天文数字。问题是f(20)你算了一遍又一遍每次从根节点下来都会重新算一次。这种重复计算就是暴力递归慢的根本原因。动态规划做的事情就一句话把已经算过的结果存起来下次直接用。存的这个“结果表”就是dp数组。1.2 从递归到dp数组的自然推导我一般建议新手先写递归再做两步改造。第一步加一个备忘录memo递归前先查表算完了存表这叫“自顶向下”的记忆化搜索。第二步把递归改成循环从最小的子问题开始往上推这叫“自底向上”的动态规划这时候的备忘录就是真正意义上的dp数组。这两步改造能让你清楚地看到dp[i]到底代表什么而不是一上来就盯着代码想破头。提示任何动态规划题如果你一时间想不出状态转移方程先试着写出暴力递归哪怕超时也无所谓递归写对了后面加备忘录和改循环都是机械操作。2. dp数组定义的核心套路先想清楚“状态”是什么很多人卡在第一步dp[i]到底存什么我的经验是你不需要去想什么高深的“状态设计理论”你只需要回答一个问题这个问题的答案跟哪些变量有关有几个关键变量dp数组就是几维的。2.1 一维dp数组的典型场景最常见的情况是问题只跟一个变化量有关。比如斐波那契数列的n爬楼梯的台阶数n最长递增子序列里的“以第i个元素结尾”。这时候一维就够了dp[i]表示“规模为 i 的子问题的答案”。但很多新手在这里容易犯一个错就是下意识把dp[i]定义成“前 i 个元素的最优解”而实际上有些题需要的是“以第 i 个元素结尾的最优解”。这两个定义差别很大。拿最长递增子序列举例如果把dp[i]定义成“前 i 个元素的最长递增子序列长度”状态转移就写不出来因为前 i 个元素的最优解不一定要包含第 i 个元素你没法确定能否接在后面。但定义成“以第 i 个元素结尾的最长递增子序列长度”dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]逻辑就顺了。2.2 二维dp数组的本质多一个约束变量当问题里有两个变化量就得用二维数组。比如01背包问题里你一边要遍历物品一边要遍历背包容量这两个都是变量那dp[i][j]就是最自然的定义前 i 件物品中选取若干件放入容量为 j 的背包能获得的最大价值。我见过很多新手在这个地方犹豫问为什么不能直接用一维数组。如果你只有一个“背包容量”变量那你确实只需要一维数组。但问题是你还得知道“当前考虑了哪些物品”。虽然你可以压缩掉物品这一维后面会细讲但理解和推导阶段二维数组是最直白的。2.3 怎么判断状态定义是否合理我给自己定过一个检验标准写完状态定义之后要能口算出dp[i][j]从哪些之前的状态推过来。如果你发现一个状态需要考虑“前面所有状态”才能推出来那通常不是状态定义错了就是状态里缺了某个关键约束。举个例子“跳跃游戏二”这种题dp[i]表示跳到第 i 个位置的最少步数转移时确实要往前扫描能跳到 i 的所有位置这是一维数组扫一遍的典型不涉及二维。但“编辑距离”这种题字符串 s 的前 i 个字符和字符串 t 的前 j 个字符两个变量必须同时出现二维数组就是唯一正解。3. 状态转移方程从“暴力递归”到“递推公式”定义好dp数组之后最核心的就是状态转移方程。这一步没有万能钥匙但有一条非常实用的经验状态转移方程其实就是“站在当前这个状态上倒推它上一个状态可能是什么样”。3.1 01背包问题的转移方程推导过程我拿01背包完整走一遍。题目说有 n 件物品每件物品有重量weight[i]和价值value[i]背包容量为cap求能装的最大价值。每件物品最多取一次这就是“01”的含义。根据前面的定义dp[i][j]表示考虑前 i 件物品、背包容量为 j 时的最大价值。现在考虑第 i 件物品这里我习惯下标从1开始方便描述。不选第 i 件物品dp[i][j] dp[i-1][j]选第 i 件物品前提是j weight[i]此时dp[i][j] dp[i-1][j - weight[i]] value[i]两者取最大就是dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])这个方程怎么理解就是站在“前 i 件物品、容量 j”这个状态问自己第 i 件物品我是拿还是不拿。不拿那答案就是前 i-1 件物品在同样容量下的最优解拿那我就得给这件物品腾出weight[i]的空间所以我先看dp[i-1][j-weight[i]]也就是前 i-1 件物品在更小容量下的最优解再加上这件物品的价值。3.2 为什么初始化是“基础用例”不是随便填新手最容易在这里出错。dp数组的初始值其实对应的是递归里的“递归出口”。如果你把状态转移方程看成一个递归函数那么当 i0 或 j0 时方程里的dp[i-1]或dp[j-weight[i]]会访问到下标 -1这就是递归没有出口会崩。所以初始化要做的事情就是把那些转移方程覆盖不到、但必然作为基础的状态先算好。当 i0 时一件物品都不考虑任何容量下价值都是 0当 j0 时背包容量为 0装不下任何东西价值也是 0于是二维数组的第一行和第一列全是 0代码里可以直接把整个数组初始化为0。但这里有个非常经典的坑如果求的是“恰好装满”的最大价值初始值就不能全是0。因为“恰好装满”意味着有些状态根本不可达如果把不可达状态初始化为0后续转移会把这些不可能的状态当成“价值为0的合法答案”传下去最后结果可能就是错的。处理方法是dp[0][0] 0其他dp[0][j] -infinity用负无穷或一个很大的负数表示不可达。这样一来只有从合法状态转移过来的结果才是有效的。注意拿到一道题先看它问的是“最大值”“最小值”还是“方案数”再看题目有没有“恰好”“刚好”这类限制这会直接决定初始化的写法。最大值通常初始化为0或负无穷最小值通常初始化为正无穷方案数通常初始化为0。3.3 求解的目标最大值还是最小化转移方向别搞反状态转移方程分两类。求最大值、求方案数通常是从小状态往大状态累加或取max。求最小值比如最少硬币数、最少编辑次数通常是从小状态加1或加cost再取min。拿完全背包问题举例dp[j]表示容量为 j 的背包能装的最大价值转移是dp[j] max(dp[j], dp[j - weight[i]] value[i])物品可以无限取所以内层循环正序遍历后面会解释。如果换成“零钱兑换”dp[j]表示凑成金额 j 的最少硬币数转移就是dp[j] min(dp[j], dp[j - coin] 1)。初始化也相应变化求最少硬币数dp[0] 0其他初始化为一个很大的数比如cap 1这样后续取min的时候不可达状态不会干扰结果。4. 遍历顺序这是背包类问题最容易被忽略的胜负手很多人把状态定义和转移方程写完一跑代码发现结果不对尤其是优化成一维数组之后问题更多。这时候90%的锅都在遍历顺序上。4.1 二维数组的遍历顺序其实没那么多讲究二维数组写法里因为dp[i][j]用到的是dp[i-1][j]和dp[i-1][j-weight[i]]都是上一行的状态所以只要保证在计算第 i 行之前第 i-1 行的所有值都已经算好了就行。无论你外层循环物品、内层循环容量还是反过来只要把行一行一行填完结果都不会错。很多教程会强调“外层物品内层容量”这个顺序是为了方便后续做空间优化而不是因为二维时这个顺序才正确。4.2 一维化之后为什么要倒序遍历容量空间优化时我们注意到dp[i][j]只依赖dp[i-1][...]也就是上一行所以没必要保留完整的二维表只保留一个一维数组滚动更新就行。但这里有个陷阱。如果内层循环用正序遍历会出现什么问题拿1维数组dp[j]来说它压缩掉的是“物品数量”这一维。当我们计算dp[j] max(dp[j], dp[j-weight[i]] value[i])时如果正序更新dp[j-weight[i]]可能已经被本轮更新过了它代表的就不是“前 i-1 件物品在容量 j-weight[i] 下的最优解”而是“前 i 件物品在容量 j-weight[i] 下的最优解”。这对01背包来说会出大事一件物品可能被使用多次也就是说01背包变成完全背包了。解决办法就是内层循环倒序遍历从cap往下走到weight[i]保证dp[j-weight[i]]仍然是上一轮也就是前 i-1 件物品的状态还没被本轮更新覆盖。我记得第一次自己推导这个结论时特意在纸上模拟了一遍。假设背包容量是5第一件物品重量2、价值3。正序遍历时dp[2]先被更新成3然后到dp[4]的时候dp[4-2]也就是dp[2]已经是3了加价值3得6相当于把第一件物品装了两遍。而01背包里第一件物品只能装一次。这就是“正序错误”的根源。4.3 完全背包和多重背包的遍历顺序完全不同完全背包因为每件物品可以无限取内层循环正序遍历就是正确的因为正序恰好允许同一个物品被重复选择。多重背包稍微复杂一点因为每件物品有数量限制不是只能取一次也不是无限取。初学者如果直接套01背包或完全背包的写法很容易出错。常见的做法是二进制拆分或单调队列优化这两个其实都是在解决“怎么在限制次数的情况下高效枚举”。我的建议是先把01背包和完全背包彻底吃透多重背包可以先用朴素拆分的写法跑通再用二进制优化降低复杂度。不要一上来就上单调队列那个对新手确实太劝退了。背包类型内层循环方向物品使用规则01背包倒序每件最多一次完全背包正序每件无限次多重背包拆分后按01背包处理每件有限次5. 从01背包出发dp数组套路如何举一反三01背包之所以经典不仅仅因为它本身常考更是因为它衍生出了一大类题型。你把它的状态定义方式吃透很多问题的底子就通了。5.1 常见变体子集划分问题力扣上有一道很经典的题“分割等和子集”。给你一个数组问能不能把它分成两个子集使得两个子集的和相等。如果你想通了01背包这道题几乎就是套模板总和为sum每个子集目标和是sum/2问题转换为能不能从数组里选一些数刚好凑出这个目标和。dp[j]表示“能否凑出和为 j”这是一个布尔数组。初始化dp[0] true表示和为0一定可以做到什么都不选。转移的时候dp[j] dp[j] || dp[j - num]内层倒序遍历和01背包一模一样。这类题我第一次做的时候特别震惊因为看起来跟“背包”八竿子打不着结果一映射思路瞬间通了。后来遇到“目标和”“最后一块石头的重量”这类题我都先试着往背包上靠命中率很高。5.2 排列与组合之外的第三类可行性判断背包类问题除了最大值、最小值还有一种就是可行性判断上一节说的“分割等和子集”就是典型。这三种问题对应的dp数组类型也不同最大价值 / 最小价值int数组存数值方案数int数组存计数转移时加和可行性bool数组存是否可达方案数和可行性的初始化也有讲究。方案数通常dp[0] 1表示“凑出0有一种方案就是什么都不取”可行性通常dp[0] true。这两种初始化的含义非常类似都是“空集合”这个基础状态是合法的。5.3 二维费用背包状态再多一维有时候背包不仅有容量限制还有重量、体积等第二重限制甚至还有“最多取 k 件”这类件数限制。这时候dp数组就得三维dp[k][i][j]表示“最多取 k 件、容量为 i、重量为 j”时的最优值。维度变多之后状态定义、转移、初始化的逻辑不会变只是代码写起来更繁琐。我的建议是这种题先用三维数组老老实实写确认逻辑没问题了再考虑滚动数组压维。不要一上来就做三维滚动优化非常容易把自己绕晕。6. 常见问题与排查技巧实录挑几个我实际踩过、也帮别人debug过的高频问题整理成速查式的心得。6.1 现象结果比正确答案大如果结果偏大第一嫌疑就是物品被重复使用了。检查点有两个一维数组内层循环是不是正序遍历了01背包的话应该倒序是否忘记处理物品体积为0的情况如果weight[i] 0正序更新会导致重复选同一个物品提示给物品重量加一个特判if weight[i] j continue可以省去很多边界上的麻烦。虽然很多模板里用j weight[i]做判断但有些时候写成for j : cap; j weight[i]; j--如果某个物品重量为0这个循环的终止条件就是j 0会无限更新。6.2 现象结果比正确答案小结果偏小多半是初始化时把不可达状态当成了合法0状态。比如“恰好装满”场景下dp[j]初始化为0导致不可达状态也被用来转移最后的值就会被低估。解决方式就是“正无穷/负无穷初始化”。我一般用一个足够大的数比如1e9来表示不可达状态不要用INT_MAX直接相加那样两个INT_MAX加起来会溢出成负数反而影响判断。6.3 现象一维滚动数组写完样例能过但提交超时滚动数组只能解决空间复杂度不能降低时间复杂度。如果时间复杂度不合格你要考虑的是一维到不了的东西比如多重背包的二进制优化、完全背包的数学优化、或者是剪枝策略。也可能是数组开小了导致越界访问。有些语言里越界访问不报错返回的是脏数据结果就“时而对时而不对”。遇到这种情况先检查下标有没有超出范围尤其注意j - weight[i]是否为负数。6.4 debug思路先打表再看每个状态是怎么来的我自己的习惯是遇到结果不对先别瞎猜把dp数组打出来跟手算或者暴力递归的结果一列一列比对。比如01背包问题打印出二维表之后你会很清楚地看到每一行的数据是从上一行继承来的还是通过选当前物品得到的。找到第一个不对的格子再去推它是从哪个状态转移过来的基本两分钟就能定位问题。这种“打表找错”的方法比对着代码看半天高效得多。尤其适合刚学dp的新手它能把抽象的转移过程变成一张你可以逐格检查的表。6.5 常见错误速查表常见问题可能原因排查方向结果偏大内层正序导致重复选物品01背包改倒序遍历结果偏小不可达状态被当成0检查“恰好”类问题初始化样例过提交超时复杂度超标考虑二进制拆分或剪枝结果不稳定数组越界访问检查下标是否非负且不越界返回0dp数组未初始化或状态不可达检查base case是否写全全部通过但心里没底状态定义太模糊打表验证转移逻辑7. 实操模板一套可复用的dp数组设计流程我把自己现在做题时的思考流程固定成了五个步骤每次遇到动态规划题都走一遍虽然不能保证一定解出来但至少不会毫无头绪。7.1 五步流程定义状态先明确有几个变量写出dp[维度]的语义并大声念一遍确认它是否覆盖了题目要求的全部信息确定base case思考递归出口在哪里哪些状态不需要转移就能确定推导转移方程问自己“当前状态是从哪个更小的状态过来的”如果想不到就试着从最后一个决策出发倒推确定遍历顺序一维数组特别注意正序还是倒序二维数组看清楚依赖的是上一行还是当前行举例验证手动算一个小例子把dp表填一遍确认与暴力结果一致7.2 一个验证用的小例子拿01背包输入weight [1, 2, 3]value [6, 10, 12]cap 5来手推二维dp表前 i 件物品容量 j容量: 0 1 2 3 4 5 i0 0 0 0 0 0 0 i1 0 6 6 6 6 6 i2 0 6 10 16 16 16 i3 0 6 10 16 18 22第3行容量为5最大值22怎么来的选了物品2重量2、价值10和物品3重量3、价值12总重量5、总价值22。再看表第二行容量为3dp[1][3]6说明只考虑第一件物品时无论容量多大都只能装它。这样一个格子一个格子地核状态转移方程对不对、遍历顺序对不对一目了然。提示在你的草稿纸上真的随手画一张这样的表比你盯着代码看半小时都有用。我到现在遇到复杂的dp都会先画表推一遍。7.3 模板代码示例01背包场景下面是01背包常规实现的代码片段分为二维和滚动数组两种写法。代码是很常见的写法但我会把关键的注释写清楚方便你对照理解刚才说的原理。# 二维dp直观易懂适合理解和调试 n len(weight) dp [[0] * (cap 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(cap 1): # 不选第 i 件物品 dp[i][j] dp[i - 1][j] # 选第 i 件物品前提容量够 if j weight[i - 1]: dp[i][j] max(dp[i][j], dp[i - 1][j - weight[i - 1]] value[i - 1])# 一维滚动数组空间优化内层必须倒序 dp [0] * (cap 1) for i in range(n): for j in range(cap, weight[i] - 1, -1): dp[j] max(dp[j], dp[j - weight[i]] value[i])这两段代码前者用来理解后者用来提交。前者代码清晰后者空间效率高。如果你连二维都调不对千万别急着改成滚动数组先打表调二维。8. 除了刷题dp数组思路能用在哪些真实场景里很多人觉得动态规划只活在面试和竞赛里现实开发中用不到。说实话日常CRUD确实用不多但有几个常见场景dp的思路是真能落地、真能提升系统质量的。8.1 资源分配的优化比如你有N个任务每个任务消耗不同的资源、产生不同的收益但总资源有限怎么选能让收益最大这就是一个标准的01背包或多重背包问题。电商后台做预算分配、广告投放做预算分配都能往这个方向抽象。8.2 文本相似度计算编辑距离Levenshtein Distance就是典型动态规划在拼写纠错、DNA序列比对、搜索词联想里都有应用。很多人在简历里写“熟练使用编辑距离算法”其实背下来很容易但真的让你推导一遍二维你就能发现它跟前面的背包问题在状态转移上是一模一样的套路。8.3 路径规划与状态机网格里从左上角到右下角有多少种走法、最短路径长度是多少是二维dp最直观的场景。游戏里的自动寻路、简单的机器人路径规划底层很多用的是这类思路。更深一层很多状态机问题比如股票买卖、任务调度也能用dp来建模因为“当前的最优决策”往往只依赖“之前的状态”不依赖具体过程。8.4 开发中遇到“取舍”问题都可以试着建模我的体会是dp模型本质上就是一种“在多步决策里求最优”的数学工具。只要问题能拆成有若干个选择、每个选择有成本/收益、有总量限制并且第 i 步的结果只依赖第 i-1 步的状态那么它大概率可以用动态规划来描述。当然实际工程里还要考虑数据量级和性能不一定真的上dp但用来做算法原型验证效率非常高。9. 准备面试或者比赛前怎么高效巩固dp数组如果你正在准备算法面试或者马上要参加算法类比赛dp是必考题型所以在考前集中刷一遍很有必要。但“刷一遍”不是随便做几十道题而是要有策略地练。9.1 按题型分组练习建议按照“一维dp → 二维dp → 背包问题 → 区间dp → 状态压缩dp”的顺序递进刷。每类题刷3-5道刷的时候不要只看通过要能自己讲出“为什么这个状态定义是对的”“为什么这个转移方程不会漏解”。有条件的可以把你讲给朋友听讲不明白的地方就是你的薄弱点。9.2 经典题目清单入门爬楼梯、打家劫舍、最大子序和一维经典最长递增子序列、最长有效括号二维经典编辑距离、最长公共子序列背包经典01背包、完全背包、分割等和子集、零钱兑换进阶区间dp戳气球、状态压缩dp旅行商问题这个清单不追求多但追求精。每一道题你要做的不是“AC了就跑”而是试着把它的状态定义、base case、转移方程、遍历顺序用前面那套五步流程完整地推导一遍再跟题解对比找差异。9.3 做题时的时间控制我个人习惯是一题想20分钟想不出来就直接看题解。不是让你死记硬背而是要你的脑子先建立“见过”的模式。动态规划题目的套路很大程度上是靠反复看题解、反复推演、形成条件反射积累起来的。别觉得看题解丢人第一次接触区间dp谁能自己想到呢看题解之后更重要的一步是合上答案自己重新写一遍而且要做到能口述整个推导过程。这才算真正吸收了一道题。动态规划这个东西刚接触时确实抽象dp数组的每个格子都像一个“加密状态”你不知道它是怎么被推出来的。但等你刷了一定数量再回头看会发现它的思维路径其实非常固定定位变量、定义dp数组、找出依赖关系、确定遍历规则、验证边界。我做题的时候最受益的一件事就是遇到不懂的地方强制自己“手推表”哪怕一题推仨小时。表格一铺开状态与状态之间的依赖关系清晰得不得了比对着题解硬背强太多。这套方法帮我把原本觉得玄学的动态规划变成了一种可以稳步复用的工具希望你也能从中找到自己的节奏。
阅读完成 · 觉得有帮助？
