动态规划这东西最难的地方从来不在“看懂”而在“想得到”。我见过太多能把背包九讲倒背如流、洛谷普及组题刷了几百道的人一遇到新题还是两眼一黑。这不是智商问题是绝大多数入门教程把动态规划讲成了“模板背诵课”爬楼梯是 f(n)f(n-1)f(n-2)01背包是 f[i][j]max(f[i-1][j], f[i-1][j- w[i]] v[i])背得滚瓜烂熟但没人告诉他 f 背后那层“状态”到底是怎么想出来的。这篇文章就是来补这一课的。它适合已经学过最基础的动态规划、知道斐波那契和背包公式、但一碰“线性dp”新题就卡壳的读者。我会把动态规划的模型原理拆开讲清楚状态设计、状态转移、边界条件这些“理论地基”再用一个车辆动态规划问题和洛谷动态规划题单带你把“理论”落成“代码”。这篇文章不讲模板讲的是从题目到递推式的整个思维过程。1. 会做模板题却做不出新题动态规划进阶的真正门槛很多人在动态规划上卡住的第一个问题不是公式记不住而是“不知道用哪套公式”。你问他最长上升子序列怎么写他能默写你给他一道“合唱队形”或者“乌龟棋”的变体他就不知道从哪下手了。这个现象太普遍了导致我一度怀疑动态规划这门课是不是就没法靠“刷题量”堆出来后来我慢慢想明白了。模板题之所以能背是因为题目已经把阶段、状态、转移都替你安排好了。而新题之所以做不出来是因为题目什么都没给你只给你一段文字描述。从文字到递推式之间隔着两件事一是你能不能判断这题能用动态规划做二是你能不能设计出正确的状态。1.1 最优子结构为什么“全局最优”可以拆成“局部最优”动态规划能成立第一个前提是问题具备最优子结构。这个概念数学书上写得很绕我更喜欢用一个粗俗但好用的比喻如果你从北京到上海的最优路线经过济南那么从济南到上海那一段一定也是从济南到上海的最优路线。道理很简单。假如济南到上海还有一条更短的路线那你把北京到济南那段拼上这条更短的路线就得到一条比“全局最优”更短的路线这就矛盾了。所以全局最优解必然是由若干个子问题的最优解拼接而成。反过来我们才能用“先求子问题的最优解再组合出父问题的最优解”这种自底向上的策略。判断一道题能不能用动态规划第一眼看的就是这个**如果你已经知道了更小规模问题的最优答案能不能在此基础上再走一步得到当前规模的答案**能就有戏不能那就不是DP题可能是贪心、搜索、或者其他什么东西。1.2 无后效性下棋不看历史只看局面第二个前提是无后效性也叫马尔可夫性。官方定义是“未来状态只与当前状态有关与过去如何到达当前状态无关”。这句话初学者最容易忽略但它恰恰是动态规划能“记忆化”的根基。我常拿下棋来类比。你下围棋的时候考虑下一步怎么走需要知道的是当前的棋盘局面而不是“刚才那十几手棋具体按什么顺序下的”。因为不同的下法顺序完全可能落到同一个局面而对未来的影响只看局面本身。动态规划也一样只要当前状态确定后面怎么转移只由这个状态决定前面是怎么走到这里的不需要再回头关心。这就解释了为什么动态规划要求状态必须“包含所有影响未来的信息”。如果状态丢掉了某个关键信息那后面做决策时信息不足转移就写不出来了。很多DP题设计状态时不知道要开几维数组本质都是在回答一个问题到底有哪些信息会影响后续决策1.3 很多“DP不会做”其实是“状态想不出来”把话说得再直白一点蛋糕在烤箱里配方都给你了很多人烤不出来是因为压根没意识到需要先切蛋糕坯子。动态规划的难点九成集中在状态定义这一步转移方程反而是水到渠成的东西。状态定义想明白了转移方程就是从状态A到状态B的一条路写不出来的概率很低状态定义想糊了后面全是灾难。这个认知一旦建立你刷题的时候关注点就会从“背转移方程”切换到“如何设计状态”而这才是真正值钱的进步。2. 状态设计把“答案”倒推成“子问题的答案”如果说动态规划是一门手艺状态设计就是这门手艺的图纸。图纸画歪了后面施工再努力也是白搭。这一节我把自己的状态设计方法论完整讲一遍都是实战里反复验证过的。2.1 状态的定义你站在哪个位置看问题我倾向于把状态理解为“我们站在哪个位置上看这个子问题”。比如斐波那契数列f(n) 的意思是“站在第 n 个台阶上回头看我自己这个子问题的答案是多少”。这个“位置”通常由一个或者几个变量刻画它们叫阶段变量。再看01背包f[i][j] 的“位置”由两个变量决定i 表示“已经考虑了前 i 件物品”j 表示“当前背包还剩 j 的容量”。这两个变量合在一起就构成了一个具体的子问题手上只有前 i 件物品可选背包容量为 j我能获取的最大价值是多少。所以设计状态的第一步是问自己题目里的决策是连续发生的吗如果是这些决策按什么顺序发生每个时刻我需要记住哪些信息才能把“现在”和“未来”切开这个问题的答案就是状态的维度。2.2 状态设计的两个极端太粗会漏信息太细会爆炸新手设计状态最常见的两个错误正好是两个极端。一个极端是状态定义得太粗。比如“dp[i] 表示前 i 件物品的最大价值”——这听起来没问题但一旦加上容量限制这个状态就丢了“当前用了多少容量”这个信息。没有容量后续的物品能不能放进去就没法判断转移自然写不出来。这种状态本质上是信息不足犯了无后效性的大忌。另一个极端是状态定义得太细。比如为了保险把所有可能的历史都塞进状态里导致状态数量指数级爆炸。我见过有人把一个小规模的线性dp题愣是定义出四五个维度复杂度算下来程序要跑到天荒地老。状态不是越全越好而是“刚好包含影响未来的全部信息”最好。多一个冗余维度复杂度就多一重指数这是要命的。一个实用经验是先把状态按直觉写出来然后对着“未来决策需要什么信息”做减法删掉那些后面不会再用的维度。比如很多题只需要知道“当前位置”和“已使用次数”那状态就是二维如果后续转移只用得到“当前位置”那一维就够。2.3 自查问题知道状态后决策是否唯一我设计完一个状态一定会问自己一个问题站在这个状态上我能不能不依赖任何额外信息就做出唯一且正确的决策举一个很典型的例子。最大子段和问题如果状态定义成“dp[i] 表示前 i 个元素的最大子段和”那从 dp[i] 到 dp[i1] 时我根本不知道当前这个最大子段和的结尾在哪里也就不知道要不要把第 i1 个元素接上去。这就是典型的“状态太粗决策不唯一”。正确做法是定义成“dp[i] 表示以第 i 个元素结尾的最大子段和”。这样站在 dp[i] 上我明确知道子段一定包含第 i 个元素那么下一步要么把第 i1 个元素接在后面要么从它自己重新开始。决策清楚了转移自然就写出来了。这个“决策是否唯一”的自查问题是我判断状态设计是否正确的黄金标准。它几乎能拦截掉八成以上的状态定义错误。你可以把它当成理论II的第一把扳手写任何状态之前先拧一下。3. 状态转移方程从最后一步决策反推出递推关系状态定义好之后下一步就是把状态之间连上线。很多教程一上来就甩出转移方程搞得像天外飞仙但其实转移方程有一个非常固定的思路考虑“最后一步”。3.1 从“最后一个决策”反推转移方程不是猜出来的什么叫从最后一步反推就是假设我现在已经站在状态 S 这个位置上我要问自己在我到达 S 之前最后做的那一个决策是什么枚举这个决策的所有可能就得到了 S 的所有前驱状态。我用数字三角形这道题来演示。题目的意思是一个三角形从顶部走到底部每次只能向下或向右下走求路径上数字和的最大值。如果我把状态定义为 dp[i][j] 表示“从顶部走到第 i 行第 j 列时能获得的最大和”那么站在 dp[i][j] 上最后一步是怎么来的只有两种可能要么从左上方的 dp[i-1][j-1] 走下来要么从正上方的 dp[i-1][j] 走下来。于是转移方程就出来了dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]你注意整个过程我没有“猜”任何东西只是老老实实地想清楚了“我到这里的最后一步是什么”。这个方法对几乎所有DP都适用包括区间dp、树形dp、状压dp只是最后一步的形式不同罢了。3.2 边界和初始化f(0)0 不是万能的和转移方程配套的是边界条件。新手最容易在这里栽跟头因为“f(0)0”在某些题里成立在另一些题里就是灾难。判断边界怎么设核心原则是边界必须能作为整个递推过程的“起点”并且符合题目的真实语义。比如数字三角形底行的 dp 值初始化为三角形底行的数字本身然后从下往上递推最后 dp[1][1] 就是答案。递推方向是自底向上的边界就在最底层。再比如最长上升子序列dp[i] 表示以第 i 个元素结尾的最长上升子序列长度那么每个 dp[i] 的初始值都是 1——因为单独一个元素本身就是一个长度为 1 的上升子序列。这里的初始化不是“f(0)0”而是“每个点先假设自己单干”。我见过很多初学者的代码边界条件要么忘初始化要么初始化的值过大过小导致答案错乱。一个老练的做法是写转移之前先用一行注释写明“dp[i] 的初始值是什么为什么”再写循环。不把话说清楚代码写着写着就会糊涂。3.3 填表顺序先把“被依赖的状态”算出来动态规划本质上是在填一张表而填表有个铁律计算 dp[i] 之前它依赖的 dp[j] 必须已经算好。这个依赖顺序通常由转移方程的结构决定。比如数字三角形从下往上推因为 dp[i][j] 依赖下一行的 dp[i1][j] 和 dp[i1][j1]而最长上升子序列要按 i 从小到大循环因为 dp[i] 依赖它前面的 dp[j]。很多题之所以要写多重循环以及循环方向要从 0 到 n 还是从 n 到 0本质上都是在保证“被依赖者先算出来”。一个小技巧如果你对循环方向没把握可以先写递归记忆化搜索也就是自顶向下。自顶向下天然不关心填表顺序因为依赖关系由递归调用自动保证。等确认了状态和转移都对再改成自底向上的递推顺便优化常数。这是我调试DP题时非常喜欢用的“双写”策略。4. 线性DP最朴素也最容易出错的DP范式聊完了通用的状态设计和转移方法论该上点具体的了。线性dp 是动态规划里最基础也最庞大的一类它的特征非常明确状态沿着一个线性序列逐步推进比如数组下标、字符串位置、时间点。很多你以为“很高端”的DP拆开看都是线性dp的变体。4.1 最大子段和状态里要不要“包含末尾”我拿最大子段和做第一个例子因为它短小精悍却能完美演示“状态定义要包含末尾”这件事。题目描述给定一个数组求一个连续子数组使得它的和最大。这个子数组至少要包含一个元素。很多人第一反应是定义 dp[i] 表示“前 i 个元素的最大子段和”但前面我已经讲过这样定义后转移时不知道当前最优子段是否在 i-1 处结束没法接续。正确状态是 dp[i] 表示“以第 i 个元素结尾的最大子段和”。转移只有两条路把第 i 个元素接到以第 i-1 个元素结尾的子段后面抛弃前面所有元素从第 i 个元素重新开一个新子段。于是dp[i] max(nums[i], dp[i-1] nums[i])这两条路分别对应“接着走”和“从头开始”。答案取所有 dp[i] 的最大值。代码很短def max_subarray(nums): dp [0] * len(nums) dp[0] nums[0] ans dp[0] for i in range(1, len(nums)): dp[i] max(nums[i], dp[i-1] nums[i]) ans max(ans, dp[i]) return ans如果你问我这个状态为什么好我的回答是它把“不知道最优子段在哪结束”这个模糊信息强行变成了“我知道一定在 i 结束”的清晰信息从而让决策唯一化。这就是状态设计的教科书案例。4.2 LIS从O(n^2)到O(n log n)的二分优化最长上升子序列是线性dp里的必考题。题目很直白给一个序列找一个最长的严格上升子序列不要求连续。朴素状态定义为 dp[i] 表示“以第 i 个元素结尾的最长上升子序列长度”。转移枚举所有在 i 之前的 j如果 nums[j] nums[i]就可以把 i 接到 j 后面dp[i] max(dp[i], dp[j] 1)初始时每个 dp[i] 1代码是双重循环复杂度 O(n^2)。def length_of_lis(nums): 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, default0)O(n^2) 能过 n5000 以内的数据。但洛谷的导弹拦截那类题数据规模一大就得换思路用“贪心 二分”把复杂度降到 O(n log n)。这个优化思路也很有意思维护一个数组 tails其中 tails[k] 表示“长度为 k1 的上升子序列的最小末尾值”。每次读入新元素 x用二分查找找到第一个大于等于 x 的位置替换掉它如果 x 比所有 tails 都大就追加到末尾。import bisect def length_of_lis_fast(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个做法的哲学是同样长度的上升子序列末尾值越小未来越有潜力。虽然 tails 数组本身并不是一个真实存在的上升子序列但它的长度就等于 LIS 的长度。这个结论不太好直观理解建议自己拿几组数据手动走一遍比背证明强。4.3 LCS二维状态和两种转移来源最长公共子序列问题则是二维线性dp的代表。给两个字符串 a 和 b求它们最长的公共子序列长度。状态定义非常自然dp[i][j] 表示“a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度”。转移分成两种情况如果 a[i-1] b[j-1]那么这两个字符可以配对dp[i][j] dp[i-1][j-1] 1否则要么忽略 a 的第 i 个字符要么忽略 b 的第 j 个字符dp[i][j] max(dp[i-1][j], dp[i][j-1])。代码def longest_common_subsequence(a, b): n, m len(a), len(b) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if a[i-1] b[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[n][m]这个转移里最有价值的思维方式是遇到不能直接配对的情况不要硬配而是分别考虑“删掉 a 的一个字符”和“删掉 b 的一个字符”这两条退路。很多二维DP题状态想出来了转移却卡住就是因为没有把“退化选择”枚举完整。我把这三个经典模型的对比放在一起方便你对照模型状态定义转移来源复杂度最大子段和dp[i]以 i 结尾的最大子段和接前一段 / 重新开始O(n)最长上升子序列dp[i]以 i 结尾的LIS长度枚举前面所有 j接在后面O(n^2)可优化至 O(n log n)最长公共子序列dp[i][j]a的前i个与b的前j个的LCS配对成功 / 删a字符 / 删b字符O(n*m)4.4 线性DP的常见翻车点线性dp看着简单翻车点却非常多。我这里列几个我自己和身边人都踩过的坑希望能帮你少走弯路。第一个坑循环方向写反。一维递推尤其容易犯比如背包问题里 01 背包要从大到小循环完全背包要从小到大循环一旦搞反物品就被无限使用了。这个坑的高级版是“滚动数组压维之后转移覆盖了还没用到的旧值”。我建议初学者老老实实先写二维跑对了再优化成一维滚动的。第二个坑状态初始化用了不合法值。比如求最小值时把 dp 初始成 0结果答案全是 0求最大值时把 dp 初始成一个大数结果答案永远是这个大数。初始化值一定得是“当前状态下最保守的合法值”通常要么是 0要么是正负无穷要么是 1比如LIS。第三个坑边界漏处理。比如数组下标从 0 开始还是从 1 开始很多转移方程在 i0 或 i1 时会访问到越界下标。我写代码前会先确认循环的下界或者在循环里加 if 判断。第四个坑也是我认为最隐蔽的状态里塞了“未来的信息”。有人写状态时不自觉用了还没计算出来的数据导致递推关系自相矛盾。这种情况通常表现为答案很怪、随机或者程序死循环。遇到这种先退一步重新审视状态定义里每个维度到底是什么时刻的信息。5. 从实际问题到DP模型用“车辆动态规划”演练一遍抽象过程很多读者学理论最头疼的是“给的是文字题不是数组题”。动态规划的模型原理恰恰是那一层“从文字到状态”的抽象。这一节我拿一个套着真实背景的“车辆动态规划问题”来做全流程演示。你不用真的懂车辆工程这个例子只是为了展示一道啰嗦的现实问题是怎么被一步步压成几行递推式的。5.1 抽象一个车辆调度问题先做减法的建模假设有这样一条运输线路一辆车从起点出发沿线有 n 个站点编号 0 到 n-1。在每个站点车可以选择停下来服务服务能获得收益 v[i]但会消耗固定时间。为了控制疲劳和充电等因素车辆不能连续停靠太密的站点——如果车在第 i 个站点停靠了那么它前面至少要有 k 个站点是直接开过、不停靠的。目标是选择一组站点停靠使得总收益最大。这种题看起来像现实中的运营调度但做算法建模时第一步永远是把与决策无关的细节剥掉。车辆是几号、司机是谁、路线是直的还是弯的这些跟“最优停靠策略”没关系统统不保留。真正影响决策的只有三件事站点顺序、每个站点的收益、相邻停靠的最小间隔约束。这一步“做减法”特别重要。很多新手拿到实际问题总想把所有背景都建模进去最后状态搞出七八维。我的建议是先建一个只包含核心约束的最小模型跑通了再回头加现实约束。算法题和工程项目不一样工程是越加越复杂做题是越拆越简单。5.2 确定阶段、状态、转移和边界决策是沿着站点顺序发生的所以阶段就是站点下标 i。那么“未来决策”需要知道什么信息只需要知道前一个停靠站点在哪里因为当前站点 i 能不能停取决于前一个停靠点是不是离得太近。但这个信息如果直接塞进状态就是二维状态 dp[i][j] 表示“前一个停靠点在 j 时处理完前 i 个站点的最大收益”显然太笨重。这里有个更好的定义dp[i] 表示“在第 i 个站点停靠时考虑前 i 个站点能获得的最大收益”。既然 dp[i] 已经保证第 i 个站点停靠了那它的前一个停靠站点 j 必须满足 i - j - 1 k也就是中间跳过至少 k 个站点。转移就是枚举所有满足条件的 jdp[i] v[i] max(dp[j])其中 j i - k - 1初始状态是每个 dp[i] 至少等于 v[i]——也就是从头到尾单独只停靠第 i 个站点。答案是所有 dp[i] 的最大值。朴素实现是 O(n^2)因为每个 i 要枚举所有可能的 j。但如果用前缀最大值思想维护“当前已经算出的 dp[j] 的最大值”就能优化到 O(n)def max_profit(stops, k): n len(stops) dp [0] * n pre_max [-10**18] * n ans 0 for i in range(n): dp[i] stops[i] if i - k - 1 0: dp[i] max(dp[i], stops[i] pre_max[i - k - 1]) pre_max[i] max(pre_max[i - 1] if i 0 else -10**18, dp[i]) ans max(ans, dp[i]) return ans看到没一个看起来无比“现实”的车辆问题在完成“做减法建模 → 定义状态 → 枚举最后一步 → 维护边界”这四步之后代码不过十几行。这就是动态规划理论基础的威力——它让你能从一堆文字里直接抓住那个递推骨架。5.3 现实约束只会更复杂留给优化的空间真实世界里的车辆动态规划问题当然不会只有“停靠间隔”这一个约束。可能还会加上每辆车的最大工作时长、站点服务的优先级、不同车辆类型的不同成本甚至充电时间窗口。约束一多状态就得多开维度比如加一维表示“当前累计已用时间”加一维表示“当前车辆是第几辆”。但请记住一条主线无论约束怎么加核心的四步走永远不变——分清决策顺序、确定影响未来的信息、定义状态、枚举最后一步。约束变多只是让“影响未来的信息”变多状态维度变多复杂度变高但思维路径没有变。我见过很多实际工程项目里的调度算法用的就是这种 DP 框架只不过维度多、数据大逼着你去用矩阵快速幂、线段树优化、单调队列优化等手段。但那些都是后话理论基础扎实了遇到复杂版本你就知道该往哪个方向加维度、加优化。6. 洛谷动态规划题单刷题顺序与自查清单理论讲了一堆如果不落到题上都是空中楼阁。洛谷的“动态规划”题单是中文社区里很经典的一套练习路线题目覆盖了从入门到进阶的几乎所有DP模型。这一节我给一份我实操过的刷题顺序和自查方法照着走会比瞎刷高效很多。6.1 建议的刷题顺序我强烈不建议一上来就刷状态压缩和斜率优化那种题会把新手自信心直接打没。合理顺序应该是先线性dp打底再背包然后区间dp最后再碰状态压缩和概率期望。我整理了一张表标出了每道题对应的考点阶段推荐题目核心考点入门P1216 数字三角形线性dp入门、自底向上递推线性dpP1020 导弹拦截LIS、不上升子序列、贪心二分线性dpP1091 合唱队形双向LIS、状态组合线性dpP1541 乌龟棋高维线性dp、状态设计背包入门P1048 采药01背包、一维滚动优化背包进阶P1616 疯狂的采药完全背包、循环方向辨析区间dpP1880 石子合并区间合并、四边形思维区间dpP1063 能量项链环形区间dp、拆环成链状态压缩P1433 吃奶酪状压dp、集合状态表示概率期望P1850 换教室概率dp、期望计算如果时间有限优先保证前面六道题彻底吃透。所谓“吃透”不只是 AC而是能把每道题的状态定义、转移理由、边界条件用一两句话讲给别人听。我一直觉得能把一道DP题讲明白比你刷十道题只求 AC 有价值得多。6.2 代码自查清单我给每一道DP题都准备了一个固定的编码检查顺序照着做能拦掉大部分低级错误状态注释在代码里用注释写清楚 dp[i] 或 dp[i][j] 到底表示什么特别注意“结尾是否必须包含当前位置”。初始化检查dp 数组的初始值是否符合“最保守合法值”。求最小值为无穷大求最大值为负无穷或 0按题目语义来。边界下标循环从几开始、到几结束会不会访问 dp[-1] 或 dp[n]。转移覆盖如果用了滚动数组检查压维后旧值是否会提前被覆盖。吃不准就先写二维。答案位置答案到底是 dp[n][m]还是 max 一下所有 dp 值。很多人在这一步丢分。这个小清单我用了很久基本上可以保证你在写代码环节不翻车。真正需要动脑子的状态设计反而在写代码之前就已经定了。6.3 调试DP的三种手段就算检查了代码也可能错。DP 题有个特点样例过了不代表你对了案例全过也可能只是运气好。我调试DP题一般用三种手段按顺序上。第一种是小数据手算。把数组缩到 4 到 6 个元素自己在纸上把 dp 表从初始值一路算到答案再和程序输出对比。这一招能揪出八成的转移错误因为你能直观看到是哪一步填错了。第二种是打印 dp 表。在循环里加个 print把每轮 dp 值打出来。别嫌日志难看它就是你的眼睛。很多状态设计问题光看答案是“神秘的错误”一看 dp 表就明白了比如某一行全是同一个数那十有八九是初始化或者转移写错了。第三种是暴力对拍。写一个最简单的暴力搜索比如枚举所有子集、DFS保证正确但很慢然后生成随机小数据把你的 DP 和暴力结果反复比对。只要有一组数据不一致就能定位到问题。这个手段在竞赛圈是基本操作但对初学者同样管用——它让你放心大胆地改代码不用怕改坏。写DP题的过程对我来说就是“状态定义花一小时转移方程花十分钟写代码花五分钟调试看状态定义又花两小时”。很多人急躁想直接跳到代码。但动态规划这门手艺功夫恰恰在代码之前的那层抽象上。最后分享一个小习惯每刷完一道动态规划题我都会在题解旁边补三行注释——这题的状态是什么、为什么这么定义、转移的“最后一步”是什么。别小看这三行字它比刷题量更能反映你是不是真的懂了。坚持一段时间你会发现拿到新题时第一时间冒出来的不再是某个模板公式而是那个藏在文字背后的状态结构。这才是“理论基础”真正开始起作用的时候。