蓝桥杯备赛笔记写到现在终于轮到了让不少人血压升高的动态规划。说实话我当年第一次接触到 DP 的时候也蒙了。在没接触 DP 之前我觉得编程就是循环、判断、套数据结构遇到问题就暴力搜索反正样例能过就行。后来真正开始刷蓝桥杯历年真题才发现有些问题暴力写法在考场上是真的过不了数据规模摆在那里逼着你必须想一个比别人更聪明的办法。这个更聪明的办法里出现频率最高的就是 DP。这篇笔记是系列里的第八篇前七篇把 Python 基础、输入输出、常用内置库、贪心、二分、搜索这些内容过了一遍这次集中聊动态规划。我会从最底层的状态定义讲起带你把背包、线性 DP、区间 DP 三大高频模型全部走一遍再用蓝桥杯真题拆解从读题到写码的完整过程最后给一份考场排错和性能优化的自查清单。适合那些刚接触 DP、或者刷了一些题但总感觉没入门的 Python 选手参考。1. 备赛视角为什么动态规划是蓝桥杯的C位考点1.1 省赛国赛里的出镜率比你想象中高拿蓝桥杯 Python 组的真题说事动态规划在省赛填空题、编程大题、国赛压轴题里都能见到。填空题里经常出现小规模路径计数、斐波那契变形之类的内容编程大题更不用说包/序列/区间这三类扛把子每年几乎轮着来。国赛里还会出现一些看起来像搜索、本质是 DP的题比如走格子加限制条件、分阶段决策的问题。所以我的结论是想拿省一背包、线性 DP 是底线想冲国奖区间 DP、高维状态设计、状态压缩这些都要能上手。DP 学得好的选手在考场上看到最大值、最小值、方案数、可行性判断这类关键词的时候天然会多一条解题路径。这个优势在比赛后期非常明显因为很多选手会用搜索硬怼最后复杂度撑不住。1.2 从裸模板题到阅读理解题命题风格在变早年蓝桥杯的 DP 题确实不算难背包模板背熟就能拿不少分那时候很多人的备赛方式就是记状态转移方程。但这几年的题风向变了出题人喜欢把 DP 藏在模拟过程或者搜索路径的外衣下面。举个例子地宫取宝这种题你第一眼看到的是走迷宫 拿东西根本不像是传统模板题但仔细一拆就会发现需要记录的状态无非是当前坐标、已经拿了几件、手里最大价值是多少。这种变化意味着什么呢意味着单纯背转移方程已经不够了你得学会自己造状态、写转移。这也是为什么我把这篇笔记的重点放在状态设计思维上而不是甩一堆模板。模板当然也要给但更重要的是让你知道这个模板是怎么来的遇到变形题的时候怎么改。1.3 我的拿分策略暴力打底记忆化加速递推定胜负很多同学一看到 DP 题就慌觉得想不出状态定义就拿不到分。我的建议是分层做别指望一步到位。第一步先用最粗暴的搜索把样例跑对。这一步不是为了拿满分而是让你彻底理解题目在做什么顺便拿一点部分分。第二步把搜索改成记忆化搜索也就是在递归里加缓存很多题目到这一步其实已经能拿到不错的分数了因为避免了重复计算。第三步如果数据范围大再把记忆化搜索改写成递推 DP做空间优化和时间优化。蓝桥杯是按测试点给分的不是非对即错。我见过不少选手死磕一个状态定义磕了四十分钟最后代码没写完。反而是那些先写暴力、然后逐步优化的选手稳稳拿了大头分数。这个策略在后面真题实战部分我会反复演示。2. DP基本功状态定义、转移方程与记忆化搜索2.1 状态定义先把什么东西在变找出来动态规划的核心不是公式而是状态设计。很多新手卡就卡在我怎么知道 dp 数组要开几维这个问题上。我的经验是拿到一道题先问自己从开始到结束有哪些东西是随着每一步在变化的每个在变化的东西都有资格成为 DP 的一个维度。拿最经典的数字三角形来说从顶部出发每次往左下或右下走路径上的数字相加求最大总和。你从起点走到某个格子 (i, j)东西收下你现在在第几行 i、第几列 j这两个是显然在变的你走了几步路径和这些也能算出或者由状态决定。所以状态就可以是 f[i][j] 表示到达第 i 行第 j 列时路径上数字的最大和。再看地宫取宝这类题你会发现在变化的东西变多了坐标 i、j拿了几件宝贝手里最大价值是多少。所以状态就是四维 f[i][j][c][v]。这就是我常说的加维度思路——限制条件越多状态维度越多直到它变成一个可以用循环填完的表。2.2 转移方程从最后一步倒推状态定义好了转移方程就是问一句话当前这个状态是从哪些上一步状态走过来的这句话特别重要。数字三角形里你到达 (i, j) 的方式只有两种从 (i-1, j-1) 向右下走或者从 (i-1, j) 向左下走。所以 f[i][j] 的答案就是这两种来源里的最大值再加上当前格子本身的数字f[i][j] max(f[i-1][j-1], f[i-1][j]) a[i][j]这就是从最后一步倒推的思维。你不用去关心整条路径长什么样只需要知道上一步在哪。另外要特别注意边界。数字三角形里每行的最左边一列只能从左上方的 (i-1, 0) 来最右边一列只能从右上方的 (i-1, i-1) 来这些位置需要单独处理不然一访问 f[i-1][j-1] 就数组越界了。边界条件也是 DP 题最容易出错的地方后面我会列一个自查清单。2.3 记忆化搜索Python 新手的试错神器说到实现方式很多教程只讲递推但我个人非常推荐新手先用记忆化搜索来验证自己的状态定义。记忆化搜索本质上就是DFS 缓存思路完全顺着递归走不用在脑子里模拟循环和数组维度的顺序。Python 里用functools.lru_cache就能轻松实现。还是数字三角形from functools import lru_cache lru_cache(maxsizeNone) def dfs(i, j): if i 0 and j 0: return tri[0][0] if j 0: return dfs(i - 1, 0) tri[i][0] if j i: return dfs(i - 1, j - 1) tri[i][i] return max(dfs(i - 1, j - 1), dfs(i - 1, j)) tri[i][j] print(max(dfs(n - 1, j) for j in range(n)))这种写法有一个好处你不需要事先想清楚完整的填表顺序只要递归关系没错lru_cache 会帮你缓存中间结果。对于考场上的快速验证来说非常省心。但要注意Python 的递归深度默认只有 1000 左右蓝桥杯的数据范围动不动上万直接递归会爆栈。考试时如果要用记忆化搜索开头加上sys.setrecursionlimit(1 25)能续命但要是递归深度实在太大还是老实转递推更稳。我在后面的 Python 性能优化部分会再展开。3. 三大高频模型背包、线性 DP、区间 DP3.1 背包问题01背包、完全背包以及倒序遍历的真正原因背包问题在蓝桥杯的出场率高到离谱其中 01 背包是绝对的基础。01 背包的模型是有 N 件物品每件物品有体积 v 和价值 w你的背包容量是 V每件物品最多选一次问能装下的最大价值。二维的状态定义是 f[i][j] 表示从前 i 件物品里选总容量不超过 j 的最大价值。转移分成两类不选第 i 件那就是 f[i-1][j]选第 i 件那就是 f[i-1][j-v[i]] w[i]。为了省空间通常写成滚动一维数组。注意一维的循环必须倒序N, V map(int, input().split()) dp [0] * (V 1) for _ in range(N): v, w map(int, input().split()) for j in range(V, v - 1, -1): dp[j] max(dp[j], dp[j - v] w) print(dp[V])为什么 01 背包必须倒序因为一维数组是复用的如果正序更新dp[j-v] 可能已经是本轮更新过的值也就是说第 i 件物品被重复使用了这正好是背包问题。只有倒序才能保证 dp[j-v] 还是上一轮的结果一件物品只取一次。那完全背包呢每件物品可以无限取循环改成正序就可以了因为正序正好允许状态在同一次遍历中反复累加同一个物品。这两个循环顺序是背包问题里的经典考点蓝桥杯不只一次考过它们的变形比如多重背包物品有限件可以拆成多个 01 背包处理、二维费用背包状态加一维因为除了容量还限制重量。记住一个核心限制条件多一维dp 数组就多一维。3.2 线性 DP最长上升子序列、最长公共子序列、编辑距离线性 DP 是指在一条线上做决策的 DP最典型的就是序列类问题。最长上升子序列LIS是蓝桥杯和各类算法比赛都爱考的问题。状态 f[i] 表示以第 i 个数结尾的最长上升子序列长度转移时往前找所有比 a[i] 小的位置n int(input()) a list(map(int, input().split())) dp [1] * n for i in range(n): for j in range(i): if a[j] a[i]: dp[i] max(dp[i], dp[j] 1) print(max(dp))这个 O(n^2) 做法在 n1000 左右是稳的但蓝桥杯有时候会把数据拉到 10 万级别这时候就得用贪心 二分优化用 tail 数组维护长度为 i 的上升子序列的最小末尾值。能掌握这个优化更稳但先说清楚不是每道 LIS 都需要优化考场上先看数据规模再决定写哪种。最长公共子序列LCS也很常见状态 f[i][j] 表示a 的前 i 个字符和 b 的前 j 个字符的 LCS 长度a input().strip() b input().strip() dp [[0] * (len(b) 1) for _ in range(len(a) 1)] for i in range(1, len(a) 1): for j in range(1, len(b) 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]) print(dp[len(a)][len(b)])每次到 (i, j)如果两个字符相等说明这个字符可以拼进公共子序列所以从 dp[i-1][j-1] 加 1如果不相等就从上方和左边取最大值。这个匹配还是不匹配的分支结构在编辑距离、回文子序列一堆问题里都会反复出现理解了 LCS这一类题基本就拿下了。3.3 区间 DP石子合并与能量项链的通用模板区间 DP 的典型特征是你处理的对象是一段连续的区间合并或者拆分时会产生代价问整体最优解。蓝桥杯里最常出现的就是石子合并和能量项链这对孪生题。石子合并的经典问题是一排石子每堆有重量每次合并相邻两堆代价是两堆重量之和问把所有石子合成一堆的最小总代价。状态 f[l][r] 表示合并第 l 堆到第 r 堆的最小代价转移时枚举一个分割点 k把 [l, r] 拆成 [l, k] 和 [k1, r] 两部分分别合并后再合并这两堆n int(input()) w list(map(int, input().split())) prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] w[i - 1] dp [[0] * n for _ in range(n)] for length in range(2, n 1): for l in range(n - length 1): r l length - 1 dp[l][r] float(inf) for k in range(l, r): cost prefix[r 1] - prefix[l] dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r] cost) print(dp[0][n - 1])区间 DP 的循环顺序非常讲究外层必须枚举区间长度 length内层枚举左端点 l再由 l 和 length 算出右端点 r最后枚举分割点 k。为什么不能直接枚举 l、r因为计算长区间时需要依赖更短区间的结果而短区间必须先算完。这个从小到大填区间的思路是区间 DP 的命根子。如果石子合并变成环形常见套路是把原数组复制一遍接在末尾然后枚举所有长度为 n 的窗口取最值。蓝桥杯能量项链那道题就是这样处理的我在下一节的真题实战里会单独演示。4. 真题实战拆解数字三角形、地宫取宝、能量项链4.1 数字三角形二维 DP 与一维滚动数组优化这道题是蓝桥杯历年真题里的入门常客题面很直白给你一个数字三角形从顶点出发每次可以向左下或右下移动走到最后一行求路径上数字之和的最大值。先给二维写法这个思路最直观n int(input()) tri [list(map(int, input().split())) for _ in range(n)] dp [[0] * n for _ in range(n)] dp[0][0] tri[0][0] for i in range(1, n): for j in range(i 1): if j 0: dp[i][j] dp[i - 1][j] tri[i][j] elif j i: dp[i][j] dp[i - 1][j - 1] tri[i][j] else: dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j]) tri[i][j] print(max(dp[n - 1]))注意边界处理最左边一列只能从上方来最右边一列只能从左上方来。最后一行所有位置都可能成为终点所以要取整行的最大值而不是只看 dp[n-1][n-1] 或者 dp[n-1][0]这是新手最容易踩的坑。如果题目数据规模再大一点二维数组可以优化成一维滚动数组。因为每一行的状态只依赖上一行而且每个位置只会被覆盖一次dp [0] * n for i in range(n): for j in range(i, -1, -1): left dp[j - 1] if j 0 else 0 dp[j] max(dp[j], left) tri[i][j] print(max(dp))这里内层倒序从右往左更新是为了保证 dp[j] 用的是上一行的旧值而不是这一行已经覆盖过的新值。滚动数组在背包问题里也用到本质上是同一个套路。有的版本里题目还会加一个限制最后路径向左下走的次数和向右下走的次数差不能超过 1。这种限制一加二维状态就不够了得加一维记录左右次数差这也是蓝桥杯喜欢玩的加维度变化。真遇到这种变体别慌先想清楚新增的限制条件是什么把它设计成状态的一维就行。4.2 地宫取宝把限制条件变成状态维度地宫取宝是蓝桥杯真题里非常能打的一道 DP 题适合用来练习高维状态设计。题目大意是这样的有一个 n 行 m 列的方格地宫每个格子里有一件宝物每件宝物价值不同。小明从左上角出发每次只能向右或向下走走到右下角为止。每到一个格子如果这个格子的宝物价值比手里已有的所有宝物价值都高他可以选择拿走也可以选择不拿。要求走到终点时手里恰好有 k 件宝物问总共有多少种不同的走法和拿法组合答案需要对一个大的取模数取模。这种题最忌讳拿到手就写搜索。我们把变的东西列出来坐标 i、j 在变手里拿了几件宝物 c 在变手里宝物的最大价值 v 在变。这三样东西加在一起就是四维状态dp[i][j][c][v]表示到达格子 (i, j)已经拿了 c 件宝物手里最大价值为 v 的方案数。因为题目里的宝物价值通常不超过 12所以 v 的范围可以只开 0 到 12其中 0 表示一件都没拿。这个离散化处理非常重要否则价值范围一大数组维度就爆炸了。转移上我习惯用向外扩散的写法从当前格子的每个状态出发向右和向下两个方向分别推进到新格子后再决定拿或不拿import sys sys.setrecursionlimit(1 25) n, m, k map(int, sys.stdin.readline().split()) g [list(map(int, sys.stdin.readline().split())) for _ in range(n)] MOD 1000000007 # dp[i][j][c][v]到达(i,j)已拿c件最大价值为v dp [[[[0] * 13 for _ in range(k 1)] for _ in range(m)] for _ in range(n)] # 起点不拿 / 拿 dp[0][0][0][0] 1 if k 1: dp[0][0][1][g[0][0]] 1 for i in range(n): for j in range(m): for c in range(k 1): for v in range(13): cur dp[i][j][c][v] if cur 0: continue # 向右走 if j 1 m: # 不拿新格子 dp[i][j 1][c][v] (dp[i][j 1][c][v] cur) % MOD # 拿新格子价值必须严格大于当前最大值 if c k and g[i][j 1] v: dp[i][j 1][c 1][g[i][j 1]] (dp[i][j 1][c 1][g[i][j 1]] cur) % MOD # 向下走 if i 1 n: dp[i 1][j][c][v] (dp[i 1][j][c][v] cur) % MOD if c k and g[i 1][j] v: dp[i 1][j][c 1][g[i 1][j]] (dp[i 1][j][c 1][g[i 1][j]] cur) % MOD ans 0 for v in range(13): ans (ans dp[n - 1][m - 1][k][v]) % MOD print(ans)这个扩散写法可能看起来有点绕但好处是思路和搜索完全一致当前格子的每一个状态都会决定下一步走到哪、以及到新格子后怎么决策。因为每个格子只能向右或向下走所以按 i、j 递增的顺序遍历不存在后效性最终所有状态都能被填满。地宫取宝的难度不在于代码本身而在于你能不能想到v这个维度。很多选手会试图用当前已拿的所有宝物和或者当前已拿宝物数量来当状态结果发现没法判断能不能拿新宝物。这正好说明了状态设计的重要性你要记录的不是已经走过的完整路径而是影响未来决策的最小信息集合。4.3 能量项链环形区间 DP 的破环成链能量项链也是蓝桥杯真题里很经典的一道区间 DP而且是从 NOIP 改编过来的很多选手在考场上一看到环形就懵。直接说结论环形区间 DP 的通用解法是破环成链把原数组复制一遍接在后面然后问题就变成了在 2n 长度的数组上做普通区间 DP。能量项链的题面大致是n 颗珠子串成环形项链每颗珠子有一个头标记和一个尾标记相邻两颗珠子可以合并合并会释放能量。因为题目细节版本很多我这里直接用区间 DP 框架来写合并代价用三个数的乘积表示左珠头、中间珠子尾、右珠尾n int(input()) a list(map(int, input().split())) a a * 2 # 破环成链 dp [[0] * (2 * n) for _ in range(2 * n)] for length in range(2, n 1): # 区间长度从 2 开始 for l in range(2 * n - length): r l length # 左闭右开区间 [l, r) for k in range(l 1, r): dp[l][r] max(dp[l][r], dp[l][k] dp[k][r] a[l] * a[k] * a[r]) ans max(dp[i][i n] for i in range(n)) print(ans)注意这里我把区间定义成左闭右开 [l, r)所以合并代价是 a[l] * a[k] * a[r]。如果你喜欢闭区间写法思路完全一样就是下标和边界细节不同选一种自己习惯的考场上别混。这种题目的核心模板就三件事枚举区间长度枚举左端点枚举分割点。把这三层循环写熟石子合并、能量项链、矩阵链乘、涂色问题全都是一个框架。重点提醒一句区分开区间和闭区间时初始化和边界条件都得跟着变否则很容易算出一堆错误答案还不自知。5. 考场实战DP 题排错、复杂度优化与 Python 性能调优5.1 常见 Bug 自查清单DP 题写错往往不是逻辑完全不搭而是某些细节出了问题。我把这几年代码调试里最常遇到的坑整理成一张表考场上对号入座问题类型典型表现解决办法数组越界访问 dp[i-1][j-1] 时 i 或 j 为 0多开一圈空间或者把下标从 1 开始编号边界未初始化dp[0][0] 或第一行第一列是默认值先手动把起点和首行首列填好循环顺序反了01 背包结果偏大检查一维背包是否倒序遍历容量区间长度没从短到长区间 DP 结果全部错乱外层必须用 length 循环终点取错数字三角形取到 dp[n-1][0]明确题目要的是最后一行任意位置还是固定右下角状态维度少了地宫取宝漏掉最大价值回到 2.1把变化的东西列全忘取模方案数题答案巨大每次累加后都对 MOD 取模递归爆栈记忆化搜索一跑就崩setrecursionlimit 或改递推这张表不需要背但建议每次卡住的时候对着看一遍。我自己刷题时有个习惯先检查边界初始化再检查循环方向最后检查转移方程里的下标符号能省下大量调试时间。5.2 复杂度估算与优化方向蓝桥杯 Python 组的时间限制一般是 1 到 2 秒能接受的运算量大概是10^7到10^8次简单操作。写 DP 前先算一下状态数和转移复杂度。比如数字三角形是 nn 个状态每个状态 O(1) 转移n1000 时是 10^6 量级完全没问题。地宫取宝是 nmk13 个状态nm50、k12 时也就 39 万左右每个状态还向外扩散两次性能完全够。但如果 nm200四维状态就变成 20020012*13约 624 万Python 里用一个巨大的四维数组会有些吃力这时候就要考虑用字典只存可达状态或者用滚动数组压掉一维。常见的优化方向有这么几个滚动数组压掉只依赖上一阶段的那一维如果状态转移只和少数几个值有关看看能不能用单调队列维护窗口最值如果方案的顺序无关紧要考虑状态压缩用二进制位表示集合。蓝桥杯大纲里状态压缩算是进阶但省一国赛可能用得上建议备赛中期再往这个方向啃。5.3 Python 考场性能优化三件套Python 在蓝桥杯里是允许用的但性能确实比 C 吃亏所以一定要养成几个好习惯。第一读入用sys.stdin.buffer.read()一次性读完再 split或者至少用sys.stdin.readline()而不是input()在循环里反复读。数据量一大input 的慢是肉眼可见的。第二能写递推就别写递归。Python 递归开销大而且深度限制容易踩坑。记忆化搜索适合验证思路最终代码尽量改成递推。第三循环里少用max(a, b)这种函数调用虽然看起来优雅但高频执行时直接if比较会更快。这不是叫你写丑陋代码而是说在大数据量题目里性能得分可能就差在这点常数上。另外如果考场支持 PyPy优先用 PyPy它的循环性能比 CPython 好不少。很多选手 Python 写的答案超时换 PyPy 提交就直接过了这个细节真的能救命。6. 备赛经验把 DP 当作填表游戏来练6.1 手推状态表的训练方法我有一个很笨但有效的方法拿到 DP 题先在纸上画出状态表格手动填前几行。比如数字三角形你就拿题目样例把 dp 表格一行行填出来观察每个格子的值是怎么从上一行推过来的。填到后面你会突然发现原来动态规划就是把一张表填完每个格子的值都来自之前已经填好的格子。这种顿悟对于新手特别重要比盯着公式看一百遍都管用。地宫取宝那种高维题没法画完整的表那就画简化版固定其中一个维度比如固定已拿 2 件然后只观察不同坐标下最大价值的变化。这种抽象推演能力是区分背模板选手和真懂 DP 选手的关键。6.2 刷题顺序与真题推荐如果你现在是从零开始备赛 DP我建议按这个顺序刷先刷斐波那契数列、爬楼梯这种一维入门题再刷数字三角形、最大子段和、LIS、LCS 这几道线性 DP接着把 01 背包和完全背包吃透包括空间优化的逆向思维然后进入区间 DP石子合并和能量项链各写三遍写到闭着眼睛能默写三层循环最后再碰地宫取宝这种高维状态题以及带状态压缩的进阶题。至于刷题来源蓝桥杯历年真题是首选C 语言、Java、Python 组的题目都能刷算法本质是一样的。LeetCode 热题 100 里的动态规划部分也可以作为日常补充那边的题目表达方式更现代能帮你拓宽状态设计的视角。但说到底最后考前一个月一定要回归真题因为蓝桥杯的题面风格和 ACM 不一样很多题是文字游戏型的读题能力本身也是要练的。我个人的体会是动态规划真的不是靠智商而是靠见多识广 刻意练习的套路。你见过了足够多的状态设计模式考场上看到新题就不会慌因为它大概率是你见过的某个模型的变形。这篇笔记把内功心法和常用招式都写出来了剩下的就是自己动手填表、写码、踩坑。下一篇系列笔记我准备聊聊图论相关的高频考点到时候咱们接着把蓝桥杯这块硬骨头往深里啃。
蓝桥杯备赛笔记写到现在终于轮到了让不少人血压升高的动态规划。说实话我当年第一次接触到 DP 的时候也蒙了。在没接触 DP 之前我觉得编程就是循环、判断、套数据结构遇到问题就暴力搜索反正样例能过就行。后来真正开始刷蓝桥杯历年真题才发现有些问题暴力写法在考场上是真的过不了数据规模摆在那里逼着你必须想一个比别人更聪明的办法。这个更聪明的办法里出现频率最高的就是 DP。这篇笔记是系列里的第八篇前七篇把 Python 基础、输入输出、常用内置库、贪心、二分、搜索这些内容过了一遍这次集中聊动态规划。我会从最底层的状态定义讲起带你把背包、线性 DP、区间 DP 三大高频模型全部走一遍再用蓝桥杯真题拆解从读题到写码的完整过程最后给一份考场排错和性能优化的自查清单。适合那些刚接触 DP、或者刷了一些题但总感觉没入门的 Python 选手参考。1. 备赛视角为什么动态规划是蓝桥杯的C位考点1.1 省赛国赛里的出镜率比你想象中高拿蓝桥杯 Python 组的真题说事动态规划在省赛填空题、编程大题、国赛压轴题里都能见到。填空题里经常出现小规模路径计数、斐波那契变形之类的内容编程大题更不用说包/序列/区间这三类扛把子每年几乎轮着来。国赛里还会出现一些看起来像搜索、本质是 DP的题比如走格子加限制条件、分阶段决策的问题。所以我的结论是想拿省一背包、线性 DP 是底线想冲国奖区间 DP、高维状态设计、状态压缩这些都要能上手。DP 学得好的选手在考场上看到最大值、最小值、方案数、可行性判断这类关键词的时候天然会多一条解题路径。这个优势在比赛后期非常明显因为很多选手会用搜索硬怼最后复杂度撑不住。1.2 从裸模板题到阅读理解题命题风格在变早年蓝桥杯的 DP 题确实不算难背包模板背熟就能拿不少分那时候很多人的备赛方式就是记状态转移方程。但这几年的题风向变了出题人喜欢把 DP 藏在模拟过程或者搜索路径的外衣下面。举个例子地宫取宝这种题你第一眼看到的是走迷宫 拿东西根本不像是传统模板题但仔细一拆就会发现需要记录的状态无非是当前坐标、已经拿了几件、手里最大价值是多少。这种变化意味着什么呢意味着单纯背转移方程已经不够了你得学会自己造状态、写转移。这也是为什么我把这篇笔记的重点放在状态设计思维上而不是甩一堆模板。模板当然也要给但更重要的是让你知道这个模板是怎么来的遇到变形题的时候怎么改。1.3 我的拿分策略暴力打底记忆化加速递推定胜负很多同学一看到 DP 题就慌觉得想不出状态定义就拿不到分。我的建议是分层做别指望一步到位。第一步先用最粗暴的搜索把样例跑对。这一步不是为了拿满分而是让你彻底理解题目在做什么顺便拿一点部分分。第二步把搜索改成记忆化搜索也就是在递归里加缓存很多题目到这一步其实已经能拿到不错的分数了因为避免了重复计算。第三步如果数据范围大再把记忆化搜索改写成递推 DP做空间优化和时间优化。蓝桥杯是按测试点给分的不是非对即错。我见过不少选手死磕一个状态定义磕了四十分钟最后代码没写完。反而是那些先写暴力、然后逐步优化的选手稳稳拿了大头分数。这个策略在后面真题实战部分我会反复演示。2. DP基本功状态定义、转移方程与记忆化搜索2.1 状态定义先把什么东西在变找出来动态规划的核心不是公式而是状态设计。很多新手卡就卡在我怎么知道 dp 数组要开几维这个问题上。我的经验是拿到一道题先问自己从开始到结束有哪些东西是随着每一步在变化的每个在变化的东西都有资格成为 DP 的一个维度。拿最经典的数字三角形来说从顶部出发每次往左下或右下走路径上的数字相加求最大总和。你从起点走到某个格子 (i, j)东西收下你现在在第几行 i、第几列 j这两个是显然在变的你走了几步路径和这些也能算出或者由状态决定。所以状态就可以是 f[i][j] 表示到达第 i 行第 j 列时路径上数字的最大和。再看地宫取宝这类题你会发现在变化的东西变多了坐标 i、j拿了几件宝贝手里最大价值是多少。所以状态就是四维 f[i][j][c][v]。这就是我常说的加维度思路——限制条件越多状态维度越多直到它变成一个可以用循环填完的表。2.2 转移方程从最后一步倒推状态定义好了转移方程就是问一句话当前这个状态是从哪些上一步状态走过来的这句话特别重要。数字三角形里你到达 (i, j) 的方式只有两种从 (i-1, j-1) 向右下走或者从 (i-1, j) 向左下走。所以 f[i][j] 的答案就是这两种来源里的最大值再加上当前格子本身的数字f[i][j] max(f[i-1][j-1], f[i-1][j]) a[i][j]这就是从最后一步倒推的思维。你不用去关心整条路径长什么样只需要知道上一步在哪。另外要特别注意边界。数字三角形里每行的最左边一列只能从左上方的 (i-1, 0) 来最右边一列只能从右上方的 (i-1, i-1) 来这些位置需要单独处理不然一访问 f[i-1][j-1] 就数组越界了。边界条件也是 DP 题最容易出错的地方后面我会列一个自查清单。2.3 记忆化搜索Python 新手的试错神器说到实现方式很多教程只讲递推但我个人非常推荐新手先用记忆化搜索来验证自己的状态定义。记忆化搜索本质上就是DFS 缓存思路完全顺着递归走不用在脑子里模拟循环和数组维度的顺序。Python 里用functools.lru_cache就能轻松实现。还是数字三角形from functools import lru_cache lru_cache(maxsizeNone) def dfs(i, j): if i 0 and j 0: return tri[0][0] if j 0: return dfs(i - 1, 0) tri[i][0] if j i: return dfs(i - 1, j - 1) tri[i][i] return max(dfs(i - 1, j - 1), dfs(i - 1, j)) tri[i][j] print(max(dfs(n - 1, j) for j in range(n)))这种写法有一个好处你不需要事先想清楚完整的填表顺序只要递归关系没错lru_cache 会帮你缓存中间结果。对于考场上的快速验证来说非常省心。但要注意Python 的递归深度默认只有 1000 左右蓝桥杯的数据范围动不动上万直接递归会爆栈。考试时如果要用记忆化搜索开头加上sys.setrecursionlimit(1 25)能续命但要是递归深度实在太大还是老实转递推更稳。我在后面的 Python 性能优化部分会再展开。3. 三大高频模型背包、线性 DP、区间 DP3.1 背包问题01背包、完全背包以及倒序遍历的真正原因背包问题在蓝桥杯的出场率高到离谱其中 01 背包是绝对的基础。01 背包的模型是有 N 件物品每件物品有体积 v 和价值 w你的背包容量是 V每件物品最多选一次问能装下的最大价值。二维的状态定义是 f[i][j] 表示从前 i 件物品里选总容量不超过 j 的最大价值。转移分成两类不选第 i 件那就是 f[i-1][j]选第 i 件那就是 f[i-1][j-v[i]] w[i]。为了省空间通常写成滚动一维数组。注意一维的循环必须倒序N, V map(int, input().split()) dp [0] * (V 1) for _ in range(N): v, w map(int, input().split()) for j in range(V, v - 1, -1): dp[j] max(dp[j], dp[j - v] w) print(dp[V])为什么 01 背包必须倒序因为一维数组是复用的如果正序更新dp[j-v] 可能已经是本轮更新过的值也就是说第 i 件物品被重复使用了这正好是背包问题。只有倒序才能保证 dp[j-v] 还是上一轮的结果一件物品只取一次。那完全背包呢每件物品可以无限取循环改成正序就可以了因为正序正好允许状态在同一次遍历中反复累加同一个物品。这两个循环顺序是背包问题里的经典考点蓝桥杯不只一次考过它们的变形比如多重背包物品有限件可以拆成多个 01 背包处理、二维费用背包状态加一维因为除了容量还限制重量。记住一个核心限制条件多一维dp 数组就多一维。3.2 线性 DP最长上升子序列、最长公共子序列、编辑距离线性 DP 是指在一条线上做决策的 DP最典型的就是序列类问题。最长上升子序列LIS是蓝桥杯和各类算法比赛都爱考的问题。状态 f[i] 表示以第 i 个数结尾的最长上升子序列长度转移时往前找所有比 a[i] 小的位置n int(input()) a list(map(int, input().split())) dp [1] * n for i in range(n): for j in range(i): if a[j] a[i]: dp[i] max(dp[i], dp[j] 1) print(max(dp))这个 O(n^2) 做法在 n1000 左右是稳的但蓝桥杯有时候会把数据拉到 10 万级别这时候就得用贪心 二分优化用 tail 数组维护长度为 i 的上升子序列的最小末尾值。能掌握这个优化更稳但先说清楚不是每道 LIS 都需要优化考场上先看数据规模再决定写哪种。最长公共子序列LCS也很常见状态 f[i][j] 表示a 的前 i 个字符和 b 的前 j 个字符的 LCS 长度a input().strip() b input().strip() dp [[0] * (len(b) 1) for _ in range(len(a) 1)] for i in range(1, len(a) 1): for j in range(1, len(b) 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]) print(dp[len(a)][len(b)])每次到 (i, j)如果两个字符相等说明这个字符可以拼进公共子序列所以从 dp[i-1][j-1] 加 1如果不相等就从上方和左边取最大值。这个匹配还是不匹配的分支结构在编辑距离、回文子序列一堆问题里都会反复出现理解了 LCS这一类题基本就拿下了。3.3 区间 DP石子合并与能量项链的通用模板区间 DP 的典型特征是你处理的对象是一段连续的区间合并或者拆分时会产生代价问整体最优解。蓝桥杯里最常出现的就是石子合并和能量项链这对孪生题。石子合并的经典问题是一排石子每堆有重量每次合并相邻两堆代价是两堆重量之和问把所有石子合成一堆的最小总代价。状态 f[l][r] 表示合并第 l 堆到第 r 堆的最小代价转移时枚举一个分割点 k把 [l, r] 拆成 [l, k] 和 [k1, r] 两部分分别合并后再合并这两堆n int(input()) w list(map(int, input().split())) prefix [0] * (n 1) for i in range(1, n 1): prefix[i] prefix[i - 1] w[i - 1] dp [[0] * n for _ in range(n)] for length in range(2, n 1): for l in range(n - length 1): r l length - 1 dp[l][r] float(inf) for k in range(l, r): cost prefix[r 1] - prefix[l] dp[l][r] min(dp[l][r], dp[l][k] dp[k 1][r] cost) print(dp[0][n - 1])区间 DP 的循环顺序非常讲究外层必须枚举区间长度 length内层枚举左端点 l再由 l 和 length 算出右端点 r最后枚举分割点 k。为什么不能直接枚举 l、r因为计算长区间时需要依赖更短区间的结果而短区间必须先算完。这个从小到大填区间的思路是区间 DP 的命根子。如果石子合并变成环形常见套路是把原数组复制一遍接在末尾然后枚举所有长度为 n 的窗口取最值。蓝桥杯能量项链那道题就是这样处理的我在下一节的真题实战里会单独演示。4. 真题实战拆解数字三角形、地宫取宝、能量项链4.1 数字三角形二维 DP 与一维滚动数组优化这道题是蓝桥杯历年真题里的入门常客题面很直白给你一个数字三角形从顶点出发每次可以向左下或右下移动走到最后一行求路径上数字之和的最大值。先给二维写法这个思路最直观n int(input()) tri [list(map(int, input().split())) for _ in range(n)] dp [[0] * n for _ in range(n)] dp[0][0] tri[0][0] for i in range(1, n): for j in range(i 1): if j 0: dp[i][j] dp[i - 1][j] tri[i][j] elif j i: dp[i][j] dp[i - 1][j - 1] tri[i][j] else: dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j]) tri[i][j] print(max(dp[n - 1]))注意边界处理最左边一列只能从上方来最右边一列只能从左上方来。最后一行所有位置都可能成为终点所以要取整行的最大值而不是只看 dp[n-1][n-1] 或者 dp[n-1][0]这是新手最容易踩的坑。如果题目数据规模再大一点二维数组可以优化成一维滚动数组。因为每一行的状态只依赖上一行而且每个位置只会被覆盖一次dp [0] * n for i in range(n): for j in range(i, -1, -1): left dp[j - 1] if j 0 else 0 dp[j] max(dp[j], left) tri[i][j] print(max(dp))这里内层倒序从右往左更新是为了保证 dp[j] 用的是上一行的旧值而不是这一行已经覆盖过的新值。滚动数组在背包问题里也用到本质上是同一个套路。有的版本里题目还会加一个限制最后路径向左下走的次数和向右下走的次数差不能超过 1。这种限制一加二维状态就不够了得加一维记录左右次数差这也是蓝桥杯喜欢玩的加维度变化。真遇到这种变体别慌先想清楚新增的限制条件是什么把它设计成状态的一维就行。4.2 地宫取宝把限制条件变成状态维度地宫取宝是蓝桥杯真题里非常能打的一道 DP 题适合用来练习高维状态设计。题目大意是这样的有一个 n 行 m 列的方格地宫每个格子里有一件宝物每件宝物价值不同。小明从左上角出发每次只能向右或向下走走到右下角为止。每到一个格子如果这个格子的宝物价值比手里已有的所有宝物价值都高他可以选择拿走也可以选择不拿。要求走到终点时手里恰好有 k 件宝物问总共有多少种不同的走法和拿法组合答案需要对一个大的取模数取模。这种题最忌讳拿到手就写搜索。我们把变的东西列出来坐标 i、j 在变手里拿了几件宝物 c 在变手里宝物的最大价值 v 在变。这三样东西加在一起就是四维状态dp[i][j][c][v]表示到达格子 (i, j)已经拿了 c 件宝物手里最大价值为 v 的方案数。因为题目里的宝物价值通常不超过 12所以 v 的范围可以只开 0 到 12其中 0 表示一件都没拿。这个离散化处理非常重要否则价值范围一大数组维度就爆炸了。转移上我习惯用向外扩散的写法从当前格子的每个状态出发向右和向下两个方向分别推进到新格子后再决定拿或不拿import sys sys.setrecursionlimit(1 25) n, m, k map(int, sys.stdin.readline().split()) g [list(map(int, sys.stdin.readline().split())) for _ in range(n)] MOD 1000000007 # dp[i][j][c][v]到达(i,j)已拿c件最大价值为v dp [[[[0] * 13 for _ in range(k 1)] for _ in range(m)] for _ in range(n)] # 起点不拿 / 拿 dp[0][0][0][0] 1 if k 1: dp[0][0][1][g[0][0]] 1 for i in range(n): for j in range(m): for c in range(k 1): for v in range(13): cur dp[i][j][c][v] if cur 0: continue # 向右走 if j 1 m: # 不拿新格子 dp[i][j 1][c][v] (dp[i][j 1][c][v] cur) % MOD # 拿新格子价值必须严格大于当前最大值 if c k and g[i][j 1] v: dp[i][j 1][c 1][g[i][j 1]] (dp[i][j 1][c 1][g[i][j 1]] cur) % MOD # 向下走 if i 1 n: dp[i 1][j][c][v] (dp[i 1][j][c][v] cur) % MOD if c k and g[i 1][j] v: dp[i 1][j][c 1][g[i 1][j]] (dp[i 1][j][c 1][g[i 1][j]] cur) % MOD ans 0 for v in range(13): ans (ans dp[n - 1][m - 1][k][v]) % MOD print(ans)这个扩散写法可能看起来有点绕但好处是思路和搜索完全一致当前格子的每一个状态都会决定下一步走到哪、以及到新格子后怎么决策。因为每个格子只能向右或向下走所以按 i、j 递增的顺序遍历不存在后效性最终所有状态都能被填满。地宫取宝的难度不在于代码本身而在于你能不能想到v这个维度。很多选手会试图用当前已拿的所有宝物和或者当前已拿宝物数量来当状态结果发现没法判断能不能拿新宝物。这正好说明了状态设计的重要性你要记录的不是已经走过的完整路径而是影响未来决策的最小信息集合。4.3 能量项链环形区间 DP 的破环成链能量项链也是蓝桥杯真题里很经典的一道区间 DP而且是从 NOIP 改编过来的很多选手在考场上一看到环形就懵。直接说结论环形区间 DP 的通用解法是破环成链把原数组复制一遍接在后面然后问题就变成了在 2n 长度的数组上做普通区间 DP。能量项链的题面大致是n 颗珠子串成环形项链每颗珠子有一个头标记和一个尾标记相邻两颗珠子可以合并合并会释放能量。因为题目细节版本很多我这里直接用区间 DP 框架来写合并代价用三个数的乘积表示左珠头、中间珠子尾、右珠尾n int(input()) a list(map(int, input().split())) a a * 2 # 破环成链 dp [[0] * (2 * n) for _ in range(2 * n)] for length in range(2, n 1): # 区间长度从 2 开始 for l in range(2 * n - length): r l length # 左闭右开区间 [l, r) for k in range(l 1, r): dp[l][r] max(dp[l][r], dp[l][k] dp[k][r] a[l] * a[k] * a[r]) ans max(dp[i][i n] for i in range(n)) print(ans)注意这里我把区间定义成左闭右开 [l, r)所以合并代价是 a[l] * a[k] * a[r]。如果你喜欢闭区间写法思路完全一样就是下标和边界细节不同选一种自己习惯的考场上别混。这种题目的核心模板就三件事枚举区间长度枚举左端点枚举分割点。把这三层循环写熟石子合并、能量项链、矩阵链乘、涂色问题全都是一个框架。重点提醒一句区分开区间和闭区间时初始化和边界条件都得跟着变否则很容易算出一堆错误答案还不自知。5. 考场实战DP 题排错、复杂度优化与 Python 性能调优5.1 常见 Bug 自查清单DP 题写错往往不是逻辑完全不搭而是某些细节出了问题。我把这几年代码调试里最常遇到的坑整理成一张表考场上对号入座问题类型典型表现解决办法数组越界访问 dp[i-1][j-1] 时 i 或 j 为 0多开一圈空间或者把下标从 1 开始编号边界未初始化dp[0][0] 或第一行第一列是默认值先手动把起点和首行首列填好循环顺序反了01 背包结果偏大检查一维背包是否倒序遍历容量区间长度没从短到长区间 DP 结果全部错乱外层必须用 length 循环终点取错数字三角形取到 dp[n-1][0]明确题目要的是最后一行任意位置还是固定右下角状态维度少了地宫取宝漏掉最大价值回到 2.1把变化的东西列全忘取模方案数题答案巨大每次累加后都对 MOD 取模递归爆栈记忆化搜索一跑就崩setrecursionlimit 或改递推这张表不需要背但建议每次卡住的时候对着看一遍。我自己刷题时有个习惯先检查边界初始化再检查循环方向最后检查转移方程里的下标符号能省下大量调试时间。5.2 复杂度估算与优化方向蓝桥杯 Python 组的时间限制一般是 1 到 2 秒能接受的运算量大概是10^7到10^8次简单操作。写 DP 前先算一下状态数和转移复杂度。比如数字三角形是 nn 个状态每个状态 O(1) 转移n1000 时是 10^6 量级完全没问题。地宫取宝是 nmk13 个状态nm50、k12 时也就 39 万左右每个状态还向外扩散两次性能完全够。但如果 nm200四维状态就变成 20020012*13约 624 万Python 里用一个巨大的四维数组会有些吃力这时候就要考虑用字典只存可达状态或者用滚动数组压掉一维。常见的优化方向有这么几个滚动数组压掉只依赖上一阶段的那一维如果状态转移只和少数几个值有关看看能不能用单调队列维护窗口最值如果方案的顺序无关紧要考虑状态压缩用二进制位表示集合。蓝桥杯大纲里状态压缩算是进阶但省一国赛可能用得上建议备赛中期再往这个方向啃。5.3 Python 考场性能优化三件套Python 在蓝桥杯里是允许用的但性能确实比 C 吃亏所以一定要养成几个好习惯。第一读入用sys.stdin.buffer.read()一次性读完再 split或者至少用sys.stdin.readline()而不是input()在循环里反复读。数据量一大input 的慢是肉眼可见的。第二能写递推就别写递归。Python 递归开销大而且深度限制容易踩坑。记忆化搜索适合验证思路最终代码尽量改成递推。第三循环里少用max(a, b)这种函数调用虽然看起来优雅但高频执行时直接if比较会更快。这不是叫你写丑陋代码而是说在大数据量题目里性能得分可能就差在这点常数上。另外如果考场支持 PyPy优先用 PyPy它的循环性能比 CPython 好不少。很多选手 Python 写的答案超时换 PyPy 提交就直接过了这个细节真的能救命。6. 备赛经验把 DP 当作填表游戏来练6.1 手推状态表的训练方法我有一个很笨但有效的方法拿到 DP 题先在纸上画出状态表格手动填前几行。比如数字三角形你就拿题目样例把 dp 表格一行行填出来观察每个格子的值是怎么从上一行推过来的。填到后面你会突然发现原来动态规划就是把一张表填完每个格子的值都来自之前已经填好的格子。这种顿悟对于新手特别重要比盯着公式看一百遍都管用。地宫取宝那种高维题没法画完整的表那就画简化版固定其中一个维度比如固定已拿 2 件然后只观察不同坐标下最大价值的变化。这种抽象推演能力是区分背模板选手和真懂 DP 选手的关键。6.2 刷题顺序与真题推荐如果你现在是从零开始备赛 DP我建议按这个顺序刷先刷斐波那契数列、爬楼梯这种一维入门题再刷数字三角形、最大子段和、LIS、LCS 这几道线性 DP接着把 01 背包和完全背包吃透包括空间优化的逆向思维然后进入区间 DP石子合并和能量项链各写三遍写到闭着眼睛能默写三层循环最后再碰地宫取宝这种高维状态题以及带状态压缩的进阶题。至于刷题来源蓝桥杯历年真题是首选C 语言、Java、Python 组的题目都能刷算法本质是一样的。LeetCode 热题 100 里的动态规划部分也可以作为日常补充那边的题目表达方式更现代能帮你拓宽状态设计的视角。但说到底最后考前一个月一定要回归真题因为蓝桥杯的题面风格和 ACM 不一样很多题是文字游戏型的读题能力本身也是要练的。我个人的体会是动态规划真的不是靠智商而是靠见多识广 刻意练习的套路。你见过了足够多的状态设计模式考场上看到新题就不会慌因为它大概率是你见过的某个模型的变形。这篇笔记把内功心法和常用招式都写出来了剩下的就是自己动手填表、写码、踩坑。下一篇系列笔记我准备聊聊图论相关的高频考点到时候咱们接着把蓝桥杯这块硬骨头往深里啃。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
