做算法专题的时候我有个习惯每到一个节点就把前面写过的笔记重新捋一遍。背包、区间、树形、状态压缩这些分支在前面都已经聊过按理说线性DP这种最基础的模型不应该在part11才拿出来讲。但现实是很多人刷了几十道DP题状态转移方程背得滚瓜烂熟遇到新题还是不知道从哪下手。问题几乎都出在同一个地方没有真正理解线性DP的模型原理只会套模板不会找“那条线”。所以这一篇我打算把线性DP单独拧出来从头到尾拆一遍模型长什么样、状态为什么那样设计、经典LIS的两副面孔、一个接近真实业务的配送调度案例最后给一份按难度分层的洛谷题单推进路线。无论你是刚开始系统刷动态规划的新手还是已经会写不少题、但总觉得“状态定义靠灵感”的人这篇应该都能给你一个能复用的思考框架。1. 线性DP的模型是什么阶段、状态与一维推进1.1 为什么“线性”这两个字才是重点线性DP叫“线性”跟线性代数没太大关系它描述的是状态推进的方向像一条线一样沿着某个维度的下标一格一格往前走。最原始的例子就是斐波那契数列f[i] f[i - 1] f[i - 2]下标从小到大推到底就得到了答案。爬楼梯、数字三角形本质上都是这个套路——状态定义在某个整数下标上转移只依赖下标更小的状态。但要注意线性DP不等于只能处理“数组序列题”。很多看起来是二维表格的题目比如过河卒、数字三角形状态推进的方向仍然是按行或者按列线性扫描并没有跳出线性DP的框架。反过来背包问题从“前i件物品”这个维度看也是线性推进的只不过它多了一个容量维度才被单独归成一类。理解这一点很重要分类只是方便讨论模型的内核是一样的。1.2 判断一道题是否适合用线性DP我自己的经验是当三个信号同时出现时大概率是线性DP输入里天然存在一个顺序比如数组下标、订单先后、比赛场次总有一个东西是按序排列的。状态可以用几个整数下标完整描述。如果状态需要记录一个集合、一棵子树才能表达清楚那往往不是线性DP。决策只依赖“当前下标之前”的信息不会依赖之后的信息也就是满足无后效性。举一个反例帮助理解区间DP里的石子合并状态是f[l][r]虽然也用下标但它依赖的是两个子区间方向是“小区间合成大区间”不是沿着一条下标线性推进所以归为区间DP。这里我把常见的DP模式整理成一张表DP类型典型阶段依赖方向无后效性如何保证线性DP序列下标i只依赖下标更小的状态按i从小到大枚举背包DP物品编号i 容量j依赖上一件物品的状态按物品顺序枚举容量定向更新区间DP区间长度len依赖更短的子区间按长度从小到大枚举树形DP树上的节点依赖子树结果DFS后序回溯返回这张表不是为了让你背类型而是帮你回答一个问题下一层枚举的变量到底是什么。线性DP最舒服的地方在于你几乎只需要回答“现在扫描到第几个了”这一个问题剩下的就是在这个答案上叠加决策。很多人刷了一堆题还是不会做是因为只记了方程没记模型。模型的第一课就是能准确说出“这道题的那条线在哪里”。2. 把题目翻译成状态线性DP核心方法论2.1 阶段、状态、决策三件套我一直觉得动态规划的全部内容就是三件事阶段、状态、决策。拿最长上升子序列LIS说阶段就是你从左往右扫描数组的位置i状态是dp[i] 以第i个位置结尾的最长上升子序列长度决策是“把i接到前面某个满足nums[j] nums[i]的子序列后面还是让它单独成为一个长度为1的子序列”。这里有一个新手特别容易踩的坑把状态定义成dp[i] 前i个元素中的最长上升子序列长度。这个定义看起来更“直观”但它丢失了关键信息。当你扫描到第i位时只知道前i-1位里最长是多少不知道这个最长子序列的末尾元素是谁也就没法判断能不能把第i位接上去。所以设计状态时一定要问自己看到这个状态值我能不能获得转移下一步所需的全部信息如果缺信息缺什么就把它补进状态里。LIS缺的是“结尾元素在哪”所以状态必须定义成“以i结尾”而不是“前i个里面”。2.2 转移方程与计算顺序无后效性从何而来状态定义好了转移方程就顺理成章dp[i] max(1, max(dp[j] 1))其中j i且nums[j] nums[i]。有几个隐藏点需要解释清楚。第一为什么要枚举所有j而不是只看i - 1因为上升子序列的前驱不一定是相邻元素任何一个下标更小、数值更小的位置都能成为前驱。可以把dp[i]理解为“站在第i位回头找所有能接上的前驱取最好的那个接上去”。第二为什么计算顺序必须从小到大因为在算dp[i]时要保证所有j i的dp[j]已经算完。这其实就是无后效性在代码顺序上的体现当前状态的决策只依赖已经确定的历史信息一旦算完就能作为后续状态的历史。如果倒过来从大到小扫dp[i]依赖的一堆dp[j]还没算出来整个递推就乱了。2.3 滚动数组与空间压缩的边界线性DP常见的空间优化是滚动数组。原理很简单如果dp[i]只依赖dp[i - 1]和dp[i - 2]那就不需要开整个数组保留最近两个值就够了。斐波那契就是最典型的例子a, b 0, 1 for i in range(2, n 1): a, b b, a b但滚动数组不是所有线性DP都能用。它成立的唯一条件是“转移只依赖连续的上一两个阶段”。LIS的转移依赖所有前面的状态那就老老实实开一维数组。判断能不能滚动不要靠记忆题型而是看方程里实际引用了哪些下标。这个习惯后面讲斜率优化时还会再次用到因为很多优化本质上就是“把转移里重复计算的量拿出来统一维护”。3. LIS的两副面孔O(N²)转移与O(NlogN)贪心二分3.1 O(N²)写法状态定义是灵魂先看朴素DP的完整实现def length_of_lis(nums): n len(nums) dp [1] * n ans 1 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) ans max(ans, dp[i]) return ans代码里有两个容易忽略的点。第一dp数组初始化成1对应“每个元素自己就是一个长度为1的上升子序列”。如果初始化成0整个答案会全员少1而且空数组的情况也会出错。第二答案是整个dp数组的最大值而不是dp[n - 1]。很多人习惯性返回最后一项遇到[1, 3, 5, 2, 4]这种数组就错了因为最长子序列1, 3, 5出现在前面dp[4]对应的子序列是1, 2, 4长度只有3。这个细节我见过太多人栽进去值得单独拿出来说。3.2 O(NlogN)的贪心二分它和DP的关系要理清当N到10^5级别O(N²)肯定超时。这时候最常见的替换方案是贪心加二分。维护一个数组dd[k]表示长度为k 1的上升子序列里末尾元素的最小值。扫描每个x时在d里找到第一个大于等于x的位置并替换成x“用尽可能小的末尾值”总是对未来更有利。import bisect def length_of_lis(nums): d [] for x in nums: pos bisect.bisect_left(d, x) if pos len(d): d.append(x) else: d[pos] x return len(d)这里要强调一点贪心二分严格来说不是线性DP它走的是贪心路线。之所以放在线性DP的专题里讲是因为它解决的是线性DP场景里最常见的性能瓶颈。另外用bisect_left还是bisect_right取决于题目要求“严格上升”还是“不下降”严格上升用bisect_left替换第一个大于等于x的位置最长不下降子序列用bisect_right替换第一个大于x的位置。这个区别值得刻在脑子里刷题时会反复用到。维度O(N²) DPO(NlogN) 贪心二分时间复杂度O(N²)O(NlogN)空间复杂度O(N)O(N)转移思路枚举所有前驱维护最小末尾值带权LIS支持不支持严格上升/不下降方程都能表达通过lower/upper_bound区分带权LIS就是每个位置除了值之外还有一个权重要求选出的上升子序列权重之和最大。这种变体没法用贪心二分只能回到DP这恰好说明了一个道理算法模板不是万能药状态设计才是核心。3.3 高频变形二维偏序与公共子序列的转化二维偏序是LIS最常见的包装。举个例子给出一组点(x, y)要求选出最长的序列使得x和y都严格递增。常规做法是先按x排序再对y做LIS。排序后x已经天然有序剩下的问题就是在一个序列上找最长上升子序列复杂度降到O(NlogN)。最长公共子序列LCS转LIS也是这类技巧里非常经典的一个。给两个排列A和B想求它们的LCS可以先记录A中每个数字出现的位置然后用这个位置信息把B映射成一个新序列再对新序列跑LIS。原理是两个序列都是排列公共子序列等价于“B中选出的元素他们在A里的相对顺序也要递增”。这个技巧在洛谷P1439里考过原题第五章会再提到。这种“把新问题映射回熟悉模型”的能力才是线性DP真正要训练的东西。4. 车辆调度问题从现实约束到一维状态4.1 一个配送站的订单该分几趟送刷题刷多了容易困在模板里所以我特意挑了一个更接近真实业务的问题来拆解。某配送站一天收到N个订单每个订单有一个地理位置而且订单必须先到先送处理顺序强制按订单编号从小到大。配送员从站点出发可以分多趟出去每趟从站点出发连续处理若干个订单处理完这一趟的所有订单后返回站点。问怎样把全部订单送完使总行驶距离最短。这个场景里“连续处理若干个订单”是关键。因为顺序强制一趟不可能跳过中间的订单先送后面的所以每一趟对应的是编号序列上的一个连续区间。整个问题就变成把1..N这个有序序列切成若干连续段每段是一趟求总代价最小。看到“切连续段”这四个字就应该立刻意识到这是分段DP也就是线性DP里非常常见的一种形态。有人可能会想每次尽量多塞订单是不是就是最优不是。订单点是分布在平面上的多塞一个订单可能让这趟绕很远所以局部贪心不成立必须用DP把可能的分段方式都枚举到。这就是为什么DP是这个问题的正确建模方式。4.2 代价函数与状态转移的推导记站点在位置0订单i的位置是pos[i]两点间的距离用dist(a, b)表示。对于从l到r的一趟订单这一趟的代价是三段路程之和cost(l, r) dist(0, pos[l]) sum(dist(pos[k], pos[k1])) dist(pos[r], 0)其中k从l到r-1。第一段是站点到第一个订单点中间段是订单点之间按顺序移动最后一段是从最后一个订单点回站点。状态定义就很好设计了dp[i]表示搞定前i个订单并且配送员已经回到站点后总行驶距离的最小值。转移时枚举上一趟的结尾jdp[i] min(dp[j] cost(j 1, i))其中j从0到i - 1dp[0] 0。这里有一个很妙的边界j 0表示这一趟从第一个订单开始“前0个订单已经搞定并回到站点”在现实里就是“还没出发”所以dp[0] 0是自然合理的初始值j i - 1表示每一趟只送一个订单所有订单一趟送完对应j 0的一次转移。所有可能的决策边界都被同一个状态覆盖了这正是DP建模完整性的体现。4.3 朴素实现、前缀和优化与更远的方向如果直接三层循环算cost复杂度是O(N³)N稍微大一点就不可行。最简单的优化是先用前缀和处理相邻订单之间的距离pre[k] sum(dist(pos[t], pos[t1]))t从1到k-1pre[0] 0。这样cost中间那段连续和就能O(1)拿到整体复杂度降到O(N²)。这个版本已经能跑通N在10^4左右的数据作为第一步足够。给一份可运行的O(N²)实现# 订单从1到npos[0]是站点 import math n 4 pos [0] [2, 4, 3, 5] # 示例数据 dist lambda a, b: abs(pos[a] - pos[b]) pre [0] * (n 1) for k in range(1, n): pre[k] pre[k - 1] dist(k, k 1) INF float(inf) dp [INF] * (n 1) dp[0] 0 for i in range(1, n 1): for j in range(i): # cost(j1, i)拆成站点-j1j1到i的相邻段i-站点 cost dist(0, j 1) (pre[i - 1] - pre[j]) dist(i, 0) dp[i] min(dp[i], dp[j] cost) print(dp[n])注意pre的下标pre[i - 1] - pre[j]算的是从j1到i-1的相邻订单距离之和正好是cost里中间那段。这段实现很短但把下标差、边界、初始化都覆盖了建议对着代码把每个变量打印一遍彻底搞懂。再往下看这个转移其实还能优化到O(N)因为cost(j 1, i)可以拆成“只与j有关的部分”加上“只与i有关的部分”扫描i时维护最小值变量就行了。这一步就是决策优化的入口part12讲斜率优化时会从这里展开。先别急着上优化建议把O(N²)版本敲出来跑通再回头看拆分思想你会对DP优化的理解更深一层。5. 用洛谷题单检验你学到的线性DP5.1 热身组数字三角形与过河卒这个题单是我按“先理解阶段再设计状态最后再上优化”的逻辑排的。第一梯队热身推荐P1216数字三角形、P1002过河卒。数字三角形里每行是一个阶段状态f[i][j]表示从顶部走到第i行第j列的最大路径和转移只依赖上一行的同列和前一列属于最基础的线性推进DP。它的教学价值在于让人体会“阶段推进”的感觉同时练到边界处理最左边和最右边的位置上一行对应的格子可能不存在编码时要处理好。过河卒是二维格路DPf[i][j] f[i - 1][j] f[i][j - 1]马的攻击位置清零。这两题都不难但请务必自己完整写一遍后面的传纸条和过河都是它们的变体。5.2 核心组导弹拦截与公共子序列转LIS第二梯队核心推荐P1020导弹拦截、P1439最长公共子序列。P1020第一问是“最长不上升子序列”把LIS模板的判断方向和二分位置改成不上升时的处理即可。第二问要求最少需要多少套拦截系统一个经典的理解是把序列划分成尽可能少的不上升子序列这个数量恰好等于最长上升子序列的长度也就是Dilworth定理在这个场景下的体现。第二问还有另一种更直观的贪心写法维护每个系统当前能拦截的最高高度对每枚导弹找第一个高度不低于它的系统并更新找不到就新开一个系统。两种做法建议都写一遍你会更理解“状态数组”在不同模型里的含义。P1439是LCS模板题。传统LCS是O(N²)的写法但这题作为训练强烈建议尝试“LCS转LIS”的做法先记录序列A中每个数字出现的位置然后用位置信息把B映射成一个新序列对新序列跑LIS。原因前面讲过两个序列都是排列公共子序列的实质就是相同元素保持相同相对顺序。做完这道题你对“模型转化”的理解会上一个台阶。5.3 进阶组传纸条、石子合并和过河第三梯队进阶推荐P1006传纸条、P1880石子合并、P1052过河。传纸条是典型的双路径线性DP。两个人同时从左上角出发要求路线不重合地到达右下角表面上是传两张纸实际上是两条并行路径。最直觉的状态是f[i1][j1][i2][j2]但观察发现两人步数相同步数为t时i1j1i2j2t可以压掉一维用f[t][i1][i2]表示两条路当前分别在哪一行。这个压缩技巧在二维格路问题里频繁出现值得记下来。石子合并是区间DP的经典题放在进阶里有点“串场”但它对理解“阶段到底是什么”帮助很大。它的阶段是区间长度状态是f[l][r]转移时把区间拆成两个子区间分别合并。环形版本可以通过复制数组变成链再做区间DP。建议做完前面的线性DP后再碰它正好衔接下一期的区间DP专题。P1052过河是更野的线性DP。青蛙从0跳到终点中间有少量石子求踩到的最少石子数。转移本身很简单dp[i] min(dp[i-k]) 当前位置是否有石子。但终点可以到极大的数量级直接开数组不行这时要用路径压缩观察发现当相邻石子间距很大时中间长距离的路段没有石子状态转移的可达结构会周期性重复把间距压缩到固定阈值后再跑DP。这道题考察的不是方程而是“状态空间里哪些部分是冗余的”非常锻炼抽象能力。5.4 刷题方法如何让每一道题都不白刷最后分享一个我一直在用的刷题流程。第一遍拿到题给自己15分钟只准想状态定义和转移方程不准写代码第二遍对照题解重点看自己的状态定义和官方解法之间的差异差异就是盲区第三遍合上题解从零写一遍完整实现第四遍隔天再重新写一遍如果还能一次写对这道题才算真正吸收。这个方法听起来笨但比一口气刷十道模板题有效得多因为你每次都在跟自己的错误模型作斗争。我个人刷完这一组后的最大体会是线性DP考到最后拉开差距的不是会不会套LIS模板而是能不能快速在题目里找出那条“线”。边界处理、初始化、下标范围这些细节写多了自然熟练但“状态里应该保留哪些信息”这个判断必须靠高强度做题才能形成直觉。如果你发现某道题卡了超过一小时不用硬啃先跳过记录问题隔一天再回来。很多时候那个顿悟的时刻比闷头刷十道题都值钱。