1. 从“暴力”到“优雅”为什么国赛选手必须掌握动态规划如果你正在备战蓝桥杯国赛或者任何一场算法竞赛那么“动态规划”这四个字绝对是你绕不开、也绝不能绕开的坎。它不是一道具体的题目而是一整套解决问题的思想武器库。很多新手一听到动态规划就觉得头大状态转移方程、最优子结构、无后效性……一堆术语砸下来感觉比直接写暴力搜索还复杂。但我想说恰恰相反动态规划是帮你从“暴力穷举”的泥潭里爬出来的那根绳子是让你从“只能过样例”到“稳稳AC”的关键一跃。在国赛级别的较量中题目数据规模动辄10^5甚至10^6O(n!)或O(2^n)的暴力搜索瞬间就会超时。这时动态规划通过“以空间换时间”将指数级复杂度降为多项式级往往是唯一正解。我见过太多选手卡在一道题上几个小时最后发现就是一个经典的DP模型变种。与其在考场上绞尽脑汁地“创造”解法不如在备赛时就把这些经典模型的骨头啃透把状态设计的套路摸清。这篇文章我就结合自己打比赛和带训的经验抛开教科书上晦涩的定义用最“实战”的方式带你梳理国赛必备的动态规划专题目标是帮你拿下这至关重要的“1/10”甚至更多。2. 动态规划核心思想化“未来”为“过去”的艺术动态规划听起来高大上但其核心思想非常朴素记住你曾经做过的事情避免重复计算。我们用一个所有竞赛生都熟悉的例子——斐波那契数列来切入。2.1 从递归爆栈到记忆化搜索DP的雏形斐波那契数列的定义是F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。最直观的做法是递归def fib(n): if n 1: return n return fib(n-1) fib(n-2)这个代码简洁但效率是灾难性的。计算fib(5)时调用树如下fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ │ ├── fib(1) │ │ │ └── fib(0) │ │ └── fib(1) │ └── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(3) ├── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(1)你会发现fib(2)、fib(3)被重复计算了无数次。时间复杂度是O(2^n)n40时计算量就已巨大。如何优化“记住过去”。我们开一个数组dpdp[i]表示斐波那契数列第i项的值。计算fib(n)时如果dp[n]已经算过就直接返回否则再计算并保存。这就是记忆化搜索Memoization是动态规划的一种自顶向下的实现方式。dp [-1] * (n1) dp[0], dp[1] 0, 1 def fib_memo(n): if dp[n] ! -1: return dp[n] dp[n] fib_memo(n-1) fib_memo(n-2) return dp[n]时间复杂度瞬间降为O(n)因为每个子问题只计算一次。2.2 递推自底向上的标准DP范式记忆化搜索仍然有递归开销。我们可以更彻底一点直接从最小的子问题开始一步步“递推”到原问题。这就是自底向上的动态规划也是最常见的DP写法。def fib_dp(n): if n 1: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]我们甚至可以不使用数组只保留前两个状态将空间复杂度优化到O(1)def fib_opt(n): if n 1: return n prev, curr 0, 1 # F(0), F(1) for i in range(2, n1): prev, curr curr, prev curr return curr注意这个例子虽然简单但它揭示了DP最本质的东西——状态定义dp[i]代表什么和状态转移方程dp[i] dp[i-1] dp[i-2]。后面所有复杂的模型都是这个套路的延伸和组合。2.3 DP解题的通用思维框架面对一道新题如何判断它是不是DP以及如何设计DP我习惯用以下四步定义状态这是最关键的一步。用一个或多个维度dp[i],dp[i][j]来表示某个子问题的解。通常状态参数直接来源于问题的变量如物品序号、背包容量、序列位置等。确定初始状态边界条件最小、最显然的子问题的解是什么比如斐波那契中的dp[0]和dp[1]。构造状态转移方程思考大问题如何由小问题推导而来。即已知dp[0...i-1]如何得到dp[i]这个方程是DP的“发动机”。确定计算顺序与答案按什么顺序计算能保证递推时所需的小状态都已求好最终答案对应哪个状态dp[n]、max(dp[...])等3. 背包问题动态规划的“第一道坎”背包问题是动态规划最经典、最模板化的领域也是国赛中的高频考点。它形象地描述了“在限制条件下进行最优选择”的过程。3.1 0/1背包每个物品的“选”与“不选”问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。每件物品只能选一次。求解将哪些物品装入背包可使总价值最大。状态定义dp[i][j]表示只考虑前i件物品在背包容量恰好为j的情况下能获得的最大价值。为什么是“恰好”初学者常用“容量不超过j”这当然也可以。但“恰好”在初始化上需要小心dp[0][0]0, 其他dp[0][j]初始化为负无穷表示不可达其好处是在处理一些变种问题时逻辑更清晰。这里我们用更常见的“不超过j”来讲解。状态转移方程对于第i件物品我们有两种选择不选那么最大价值就是只考虑前i-1件物品、容量为j时的价值即dp[i-1][j]。选前提是j v[i]那么最大价值是“只考虑前i-1件物品、容量为j-v[i]时的最大价值”加上本物品的价值即dp[i-1][j-v[i]] w[i]。 我们取两者的最大值dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])。初始化dp[0][j] 0表示不考虑任何物品时任何容量的最大价值都是0。计算顺序外层循环遍历物品i从1到N内层循环遍历背包容量j从0到V。答案dp[N][V]。代码实现二维数组N, V map(int, input().split()) v [0] * (N1) w [0] * (N1) for i in range(1, N1): v[i], w[i] map(int, input().split()) dp [[0]*(V1) for _ in range(N1)] for i in range(1, N1): for j in range(V1): dp[i][j] dp[i-1][j] # 不选 if j v[i]: dp[i][j] max(dp[i][j], dp[i-1][j-v[i]] w[i]) print(dp[N][V])3.2 空间优化滚动数组与一维数组观察状态转移方程dp[i][j]只依赖于dp[i-1][...]即上一行。这意味着我们不需要保存整个二维数组只需要保存“上一行”和“当前行”即可这就是滚动数组空间复杂度从O(NV)降到O(2V)。更进一步如果我们内层循环从大到小遍历容量j那么连滚动数组都不需要可以直接用一个一维数组覆盖更新。为什么必须逆序因为dp[j]更新时需要用到dp[j-v[i]]这个值是“上一轮i-1”状态下的值。如果正序遍历当更新dp[j]时dp[j-v[i]]可能已经被本轮的更新覆盖了这就相当于同一件物品被选了多次变成了“完全背包”的逻辑。逆序遍历保证了在更新dp[j]时dp[j-v[i]]还是“上一轮”的值。一维数组优化代码dp [0] * (V1) for i in range(1, N1): for j in range(V, v[i]-1, -1): # 逆序遍历 dp[j] max(dp[j], dp[j - v[i]] w[i]) print(dp[V])这是竞赛中最常见的0/1背包写法务必熟练掌握。3.3 完全背包与多重背包基于0/1的扩展完全背包每件物品可以选无限次。 状态转移方程dp[i][j] max(dp[i-1][j], dp[i][j-v[i]] w[i])。 注意与0/1背包的区别选择物品i时是从dp[i][j-v[i]]转移而来因为物品i选了之后还能再选。一维优化后内层循环正序遍历即可。for i in range(1, N1): for j in range(v[i], V1): # 正序遍历 dp[j] max(dp[j], dp[j - v[i]] w[i])多重背包第i件物品最多可以选s[i]次。 最朴素的想法是把它拆成s[i]个独立的0/1背包物品但这样复杂度是O(V*Σs[i])可能太高。二进制优化将s[i]拆分成1, 2, 4, ..., 2^k, c其中c是剩余部分这样若干个“物品包”每个包视为一个独立的0/1物品。因为任何数量都可以由这些2的幂次组合而成。这样物品总数从Σs[i]降为Σlog(s[i])再套用0/1背包即可。单调队列优化可以进一步将复杂度优化到O(NV)是更高级的优化国赛有可能考到其思想。实操心得背包问题的变种极多比如求方案数、求具体方案、二维费用背包体积重量、分组背包每组内最多选一个等。核心在于准确理解状态定义和设计正确的转移方程。刷题时建议先彻底搞懂0/1背包的一维写法然后对比理解完全背包的正序原因最后攻克多重背包的二进制拆分。蓝桥杯真题里《包子凑数》就是一个结合了完全背包和数论的好题。4. 线性DP序列与字符串问题的利器线性DP是指状态沿着一个线性维度如序列长度、时间推进的DP。最长上升子序列LIS和最长公共子序列LCS是其代表。4.1 最长上升子序列LIS两种经典解法问题描述给定一个长度为N的数列求数值严格单调递增的子序列的长度最长是多少。解法一朴素DPO(n²)状态定义dp[i]表示以第i个数字结尾的最长上升子序列的长度。转移方程dp[i] max(dp[j]) 1其中0 j i且a[j] a[i]。意思是在i之前找一个结尾比a[i]小的子序列接上a[i]。初始化每个位置至少可以以自己结尾长度为1所以dp[i] 1。答案max(dp[0...n-1])。n len(a) 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 log n)这是竞赛中的标准最优解法必须掌握。维护一个数组tailtail[len]表示长度为len的上升子序列中末尾元素的最小值。这个数组本身是严格递增的。过程遍历每个数x在tail中找到第一个大于等于x的位置pos二分查找。如果pos是当前tail的长度即x比所有末尾都大则x可以接在后面使最长长度1。否则用x替换tail[pos]。因为对于同样长度为pos1的子序列一个更小的末尾值x比原来的tail[pos]“潜力”更大更容易让后面的数接上。答案最终tail数组的长度就是LIS的长度。import bisect tail [] for x in a: pos bisect.bisect_left(tail, x) # 找到第一个 x 的位置 if pos len(tail): tail.append(x) else: tail[pos] x print(len(tail))注意这个方法求出的是长度tail数组本身不一定是一个合法的LIS它只维护了各种长度的最小末尾。如果需要输出具体序列通常还是用O(n²)的DP并记录前驱。4.2 最长公共子序列LCS二维状态设计问题描述给定两个字符串A和B求它们的最长公共子序列不要求连续的长度。状态定义dp[i][j]表示字符串A的前i个字符A[0:i]和字符串B的前j个字符B[0:j]的LCS长度。转移方程如果A[i-1] B[j-1]那么最后一个字符可以匹配dp[i][j] dp[i-1][j-1] 1。如果A[i-1] ! B[j-1]那么最后一个字符不匹配LCS长度取决于“不要A的最后一个字符”或“不要B的最后一个字符”中的最大值即dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始化dp[0][j] dp[i][0] 0表示一个空串与任何串的LCS长度为0。答案dp[len(A)][len(B)]。m, n len(A), len(B) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): 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[m][n])空间优化同样可以优化到一维但需要用一个变量保存dp[i-1][j-1]因为新的dp[j]即dp[i][j]需要它。代码会稍复杂在竞赛中如果内存不紧张直接用二维更清晰。4.3 编辑距离LCS的扩展编辑距离Levenshtein距离是LCS的一个变种操作包括增、删、改。其DP定义与LCS类似dp[i][j]表示将A的前i个字符变成B的前j个字符所需的最少操作次数。转移方程增dp[i][j] dp[i][j-1] 1(在A末尾插入B[j-1])删dp[i][j] dp[i-1][j] 1(删除A[i-1])改dp[i][j] dp[i-1][j-1] (0 if A[i-1]B[j-1] else 1)(如果相同则不改不同则替换一次)dp[i][j]取三者最小值。初始化dp[i][0] i(删i次)dp[0][j] j(增j次)。5. 区间DP与状态机DP处理复杂依赖关系当子问题不是简单的线性顺序而是涉及区间或复杂的状态切换时就需要更高级的DP模型。5.1 区间DP枚举分割点的艺术区间DP常用于处理合并类或回文类问题状态通常定义为dp[l][r]表示区间[l, r]上的最优解或可行性。经典例题石子合并有N堆石子排成一排每次只能合并相邻的两堆代价是两堆石子数之和。求将所有石子合并成一堆的最小总代价。状态定义dp[l][r]表示将区间[l, r]内的所有石子合并成一堆的最小代价。转移方程考虑最后一次合并它一定是将[l, r]分成的左右两堆[l, k]和[k1, r]合并起来。所以我们需要枚举这个分割点k。dp[l][r] min(dp[l][k] dp[k1][r]) sum[l][r], 其中l k r。 这里sum[l][r]是区间[l, r]的石子总数因为合并左右两堆的代价就是它们的总重量。可以用前缀和快速计算。初始化dp[i][i] 0单堆石子不需要合并。计算顺序这是关键。因为计算大区间[l, r]需要用到它内部的更小区间所以我们必须按区间长度len从小到大的顺序来递推。先算所有长度为2的区间再算长度为3的直到长度为N。答案dp[1][N]。n len(stones) prefix_sum [0] * (n1) for i in range(1, n1): prefix_sum[i] prefix_sum[i-1] stones[i-1] dp [[0]* (n1) for _ in range(n1)] # 初始化已在创建时完成全0dp[i][i]0 for length in range(2, n1): # 枚举区间长度 for l in range(1, n-length2): # 枚举左端点 r l length - 1 dp[l][r] float(inf) # 初始化为无穷大 sum_lr prefix_sum[r] - prefix_sum[l-1] for k in range(l, r): # 枚举分割点 dp[l][r] min(dp[l][r], dp[l][k] dp[k1][r] sum_lr) print(dp[1][n])时间复杂度O(n³)。有一个叫“四边形不等式”的优化可以降到O(n²)但国赛中能写出O(n³)通常足够。5.2 状态机DP描述“状态”的流转有些问题中一个对象有多个不同的“状态”决策会影响状态的转移。用状态机模型来设计DP会非常清晰。经典例题股票买卖系列含冷冻期题目你可以进行多次交易买卖为一笔交易但卖出股票后有一天的冷冻期不能第二天买入。求最大利润。状态定义每天结束时我们可能处于三种状态之一dp[i][0]: 第i天结束时持有股票的最大利润。dp[i][1]: 第i天结束时不持有股票且处于冷冻期即今天卖出了股票的最大利润。dp[i][2]: 第i天结束时不持有股票且不处于冷冻期的最大利润。状态转移dp[i][0]今天持有股票可能是昨天就持有(dp[i-1][0])也可能是今天刚买入。今天买入的前提是昨天不持有且不处于冷冻期(dp[i-1][2])。所以dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])。dp[i][1]今天卖出了股票所以昨天必须持有股票。dp[i][1] dp[i-1][0] prices[i]。dp[i][2]今天不持有也不在冷冻期说明昨天也没持有股票。昨天可能处于冷冻期(dp[i-1][1])或非冷冻期(dp[i-1][2])。dp[i][2] max(dp[i-1][1], dp[i-1][2])。初始化dp[0][0] -prices[0](第一天买入)dp[0][1] 0(第一天不可能卖出)dp[0][2] 0(第一天不操作)答案最后一天不可能持有股票持有未卖出是亏损的所以答案是max(dp[n-1][1], dp[n-1][2])。n len(prices) dp [[0]*3 for _ in range(n)] dp[0][0] -prices[0] for i in range(1, n): dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] dp[i-1][0] prices[i] dp[i][2] max(dp[i-1][1], dp[i-1][2]) print(max(dp[n-1][1], dp[n-1][2]))这种建模方式将复杂的条件冷冻期清晰地转化为状态间的转移规则是解决此类问题的利器。6. 树形DP与状压DP应对更复杂的结构6.1 树形DP在树上做选择树形DP通常用递归DFS的方式实现因为树的结构天然适合递归遍历。核心思想是后序遍历先处理所有子树得到子树的信息再结合根节点做出决策。经典例题没有上司的舞会公司有N个人关系是树形结构。每个人有一个快乐值。直接上司和下属不能同时参加舞会。求最大的快乐值之和。状态定义dp[u][0]表示以u为根的子树且u不参加舞会时子树的最大快乐值。dp[u][1]表示u参加舞会时子树的最大快乐值。转移方程如果u不参加(dp[u][0])那么它的子节点v可以参加也可以不参加我们取最大值累加dp[u][0] max(dp[v][0], dp[v][1])。如果u参加(dp[u][1])那么它的子节点v一定不能参加dp[u][1] dp[v][0]。 最后dp[u][1]还要加上u自己的快乐值。初始化对于叶子节点dp[leaf][0]0,dp[leaf][1]happy[leaf]。计算顺序通过DFS从叶子节点向上递推。答案max(dp[root][0], dp[root][1])。import sys sys.setrecursionlimit(100000) # 防止递归深度过大 def dfs(u): dp[u][1] happy[u] # 初始化选择u的快乐值 for v in children[u]: dfs(v) # 先处理子树 dp[u][0] max(dp[v][0], dp[v][1]) dp[u][1] dp[v][0] # 假设已建好树结构children找到根节点root dfs(root) print(max(dp[root][0], dp[root][1]))6.2 状压DP用二进制表示集合状态当问题的规模较小通常n 20并且涉及“选择”或“排列”时可以用一个整数的二进制位来表示一个集合进行状态压缩。经典例题旅行商问题TSP的DP解法有n个城市给出任意两城市间的距离。从城市0出发每个城市访问一次后回到0求最短路径。状态定义dp[S][i]表示已经访问过的城市集合为S二进制状态压缩并且当前位于城市i的最短路径长度。例如S1011(二进制)表示城市0,1,3已访问。转移方程考虑当前状态(S, i)下一步要去一个还没去过的城市j。则dp[S|(1j)][j] min(dp[S|(1j)][j], dp[S][i] dist[i][j])。初始化dp[1][0] 0表示从城市0出发只访问了城市0当前在0距离为0。其他状态初始化为无穷大。计算顺序按集合S的大小即已访问城市数量从小到大递推。答案访问完所有城市后再回到0。即min(dp[(1n)-1][i] dist[i][0])对所有i取最小值。n 4 dist [[0,2,6,5],[2,0,4,4],[6,4,0,2],[5,4,2,0]] # 示例距离矩阵 INF float(inf) dp [[INF]*n for _ in range(1n)] dp[1][0] 0 # 从0号城市出发 for S in range(1n): # 遍历所有状态 for i in range(n): if dp[S][i] INF: # 状态不可达 continue if not (S i) 1: # 当前城市i不在集合S中理论上不会发生但检查一下 continue for j in range(n): if (S j) 1: # 城市j已经访问过 continue new_S S | (1 j) dp[new_S][j] min(dp[new_S][j], dp[S][i] dist[i][j]) ans INF for i in range(n): ans min(ans, dp[(1n)-1][i] dist[i][0]) print(ans)状压DP的难点在于对二进制操作要非常熟练并且要能设计出合理的状态表示。7. 国赛真题实战分析与避坑指南动态规划在蓝桥杯国赛中几乎每年必考且常作为压轴题或难题出现。下面结合常见考点和我的踩坑经验总结几点实战要点。7.1 识别DP问题的特征拿到题目如何快速判断可能是DP求最值最大/最小数量、最大/最小代价、最长/最短长度等。计数问题求方案总数、路径数等且通常有取模要求。可行性问题问“是否可能”、“能否达成”。数据范围暗示n在10^2到10^3级别可能对应O(n²)或O(n³)的DPn在20左右可能对应状压DP O(n2^n)。问题具有重叠子问题暴力搜索会重复计算很多相同情况。问题具有最优子结构大问题的最优解可以由小问题的最优解推导出来。7.2 状态设计是灵魂初始化是根基状态设计宁多勿少在时间空间允许的情况下多开一维状态让转移更清晰远比为了省空间而设计一个晦涩的状态要好。比如处理“恰好”vs“不超过”的问题多一维状态可能更直观。初始化要小心特别是求最小值时通常初始化为一个很大的数如float(inf)但起点状态要初始化为0或合法值。求“恰好”装满背包的方案数时dp[0]1其他dp[j]0。注意下标偏移题目给的索引从0开始还是1开始dp数组通常从0或1开始要统一避免IndexError。我个人的习惯是在输入时就把数据读到下标1开始的位置这样思维上更连贯。7.3 调试与对拍技巧DP代码写出来如果样例没过或者感觉不对怎么调试打印DP表对于二维DP把整个dp数组打印出来与手算的小规模样例对比。这是最直接有效的方法。缩小数据规模自己构造一个n3或4的极小样例手动模拟整个过程再与程序输出对比。对拍写一个绝对正确但很慢的暴力搜索DFS程序用于小数据范围n15的随机测试。生成随机输入分别运行DP程序和暴力程序对比结果。这是竞赛中验证算法正确性的黄金标准。关注边界检查i0,j0,S0这些边界状态是否正确初始化转移时是否越界。7.4 时间与空间复杂度的权衡空间优化在确定一维优化正确无误后再进行。国赛环境通常宽松如果没把握用二维数组更稳妥。剪枝在DP循环中如果某些状态明显不可能转移到最终答案可以提前continue。例如在背包问题中内层循环可以从v[i]开始而不是从0开始。避免不必要的计算比如区间DP中前缀和可以预处理不要在循环里重复求和。动态规划的学习没有捷径就是“理解模型 - 刷经典题 - 总结归纳 - 挑战变形题”的循环。国赛在即建议你把本文提到的每个经典模型都去找2-3道蓝桥杯真题或高质量练习题巩固。写代码时先自己思考状态设计和转移方程卡住了再看题解这样收获最大。记住在考场上一个清晰的、哪怕不是最优的DP思路也比一个模糊的“贪心”猜想更有机会得分。祝你备赛顺利国赛夺魁 蓝桥杯国赛必备：动态规划核心思想与经典模型实战解析
1. 从“暴力”到“优雅”为什么国赛选手必须掌握动态规划如果你正在备战蓝桥杯国赛或者任何一场算法竞赛那么“动态规划”这四个字绝对是你绕不开、也绝不能绕开的坎。它不是一道具体的题目而是一整套解决问题的思想武器库。很多新手一听到动态规划就觉得头大状态转移方程、最优子结构、无后效性……一堆术语砸下来感觉比直接写暴力搜索还复杂。但我想说恰恰相反动态规划是帮你从“暴力穷举”的泥潭里爬出来的那根绳子是让你从“只能过样例”到“稳稳AC”的关键一跃。在国赛级别的较量中题目数据规模动辄10^5甚至10^6O(n!)或O(2^n)的暴力搜索瞬间就会超时。这时动态规划通过“以空间换时间”将指数级复杂度降为多项式级往往是唯一正解。我见过太多选手卡在一道题上几个小时最后发现就是一个经典的DP模型变种。与其在考场上绞尽脑汁地“创造”解法不如在备赛时就把这些经典模型的骨头啃透把状态设计的套路摸清。这篇文章我就结合自己打比赛和带训的经验抛开教科书上晦涩的定义用最“实战”的方式带你梳理国赛必备的动态规划专题目标是帮你拿下这至关重要的“1/10”甚至更多。2. 动态规划核心思想化“未来”为“过去”的艺术动态规划听起来高大上但其核心思想非常朴素记住你曾经做过的事情避免重复计算。我们用一个所有竞赛生都熟悉的例子——斐波那契数列来切入。2.1 从递归爆栈到记忆化搜索DP的雏形斐波那契数列的定义是F(0)0, F(1)1, F(n)F(n-1)F(n-2) (n2)。最直观的做法是递归def fib(n): if n 1: return n return fib(n-1) fib(n-2)这个代码简洁但效率是灾难性的。计算fib(5)时调用树如下fib(5) ├── fib(4) │ ├── fib(3) │ │ ├── fib(2) │ │ │ ├── fib(1) │ │ │ └── fib(0) │ │ └── fib(1) │ └── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(3) ├── fib(2) │ ├── fib(1) │ └── fib(0) └── fib(1)你会发现fib(2)、fib(3)被重复计算了无数次。时间复杂度是O(2^n)n40时计算量就已巨大。如何优化“记住过去”。我们开一个数组dpdp[i]表示斐波那契数列第i项的值。计算fib(n)时如果dp[n]已经算过就直接返回否则再计算并保存。这就是记忆化搜索Memoization是动态规划的一种自顶向下的实现方式。dp [-1] * (n1) dp[0], dp[1] 0, 1 def fib_memo(n): if dp[n] ! -1: return dp[n] dp[n] fib_memo(n-1) fib_memo(n-2) return dp[n]时间复杂度瞬间降为O(n)因为每个子问题只计算一次。2.2 递推自底向上的标准DP范式记忆化搜索仍然有递归开销。我们可以更彻底一点直接从最小的子问题开始一步步“递推”到原问题。这就是自底向上的动态规划也是最常见的DP写法。def fib_dp(n): if n 1: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]我们甚至可以不使用数组只保留前两个状态将空间复杂度优化到O(1)def fib_opt(n): if n 1: return n prev, curr 0, 1 # F(0), F(1) for i in range(2, n1): prev, curr curr, prev curr return curr注意这个例子虽然简单但它揭示了DP最本质的东西——状态定义dp[i]代表什么和状态转移方程dp[i] dp[i-1] dp[i-2]。后面所有复杂的模型都是这个套路的延伸和组合。2.3 DP解题的通用思维框架面对一道新题如何判断它是不是DP以及如何设计DP我习惯用以下四步定义状态这是最关键的一步。用一个或多个维度dp[i],dp[i][j]来表示某个子问题的解。通常状态参数直接来源于问题的变量如物品序号、背包容量、序列位置等。确定初始状态边界条件最小、最显然的子问题的解是什么比如斐波那契中的dp[0]和dp[1]。构造状态转移方程思考大问题如何由小问题推导而来。即已知dp[0...i-1]如何得到dp[i]这个方程是DP的“发动机”。确定计算顺序与答案按什么顺序计算能保证递推时所需的小状态都已求好最终答案对应哪个状态dp[n]、max(dp[...])等3. 背包问题动态规划的“第一道坎”背包问题是动态规划最经典、最模板化的领域也是国赛中的高频考点。它形象地描述了“在限制条件下进行最优选择”的过程。3.1 0/1背包每个物品的“选”与“不选”问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。每件物品只能选一次。求解将哪些物品装入背包可使总价值最大。状态定义dp[i][j]表示只考虑前i件物品在背包容量恰好为j的情况下能获得的最大价值。为什么是“恰好”初学者常用“容量不超过j”这当然也可以。但“恰好”在初始化上需要小心dp[0][0]0, 其他dp[0][j]初始化为负无穷表示不可达其好处是在处理一些变种问题时逻辑更清晰。这里我们用更常见的“不超过j”来讲解。状态转移方程对于第i件物品我们有两种选择不选那么最大价值就是只考虑前i-1件物品、容量为j时的价值即dp[i-1][j]。选前提是j v[i]那么最大价值是“只考虑前i-1件物品、容量为j-v[i]时的最大价值”加上本物品的价值即dp[i-1][j-v[i]] w[i]。 我们取两者的最大值dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])。初始化dp[0][j] 0表示不考虑任何物品时任何容量的最大价值都是0。计算顺序外层循环遍历物品i从1到N内层循环遍历背包容量j从0到V。答案dp[N][V]。代码实现二维数组N, V map(int, input().split()) v [0] * (N1) w [0] * (N1) for i in range(1, N1): v[i], w[i] map(int, input().split()) dp [[0]*(V1) for _ in range(N1)] for i in range(1, N1): for j in range(V1): dp[i][j] dp[i-1][j] # 不选 if j v[i]: dp[i][j] max(dp[i][j], dp[i-1][j-v[i]] w[i]) print(dp[N][V])3.2 空间优化滚动数组与一维数组观察状态转移方程dp[i][j]只依赖于dp[i-1][...]即上一行。这意味着我们不需要保存整个二维数组只需要保存“上一行”和“当前行”即可这就是滚动数组空间复杂度从O(NV)降到O(2V)。更进一步如果我们内层循环从大到小遍历容量j那么连滚动数组都不需要可以直接用一个一维数组覆盖更新。为什么必须逆序因为dp[j]更新时需要用到dp[j-v[i]]这个值是“上一轮i-1”状态下的值。如果正序遍历当更新dp[j]时dp[j-v[i]]可能已经被本轮的更新覆盖了这就相当于同一件物品被选了多次变成了“完全背包”的逻辑。逆序遍历保证了在更新dp[j]时dp[j-v[i]]还是“上一轮”的值。一维数组优化代码dp [0] * (V1) for i in range(1, N1): for j in range(V, v[i]-1, -1): # 逆序遍历 dp[j] max(dp[j], dp[j - v[i]] w[i]) print(dp[V])这是竞赛中最常见的0/1背包写法务必熟练掌握。3.3 完全背包与多重背包基于0/1的扩展完全背包每件物品可以选无限次。 状态转移方程dp[i][j] max(dp[i-1][j], dp[i][j-v[i]] w[i])。 注意与0/1背包的区别选择物品i时是从dp[i][j-v[i]]转移而来因为物品i选了之后还能再选。一维优化后内层循环正序遍历即可。for i in range(1, N1): for j in range(v[i], V1): # 正序遍历 dp[j] max(dp[j], dp[j - v[i]] w[i])多重背包第i件物品最多可以选s[i]次。 最朴素的想法是把它拆成s[i]个独立的0/1背包物品但这样复杂度是O(V*Σs[i])可能太高。二进制优化将s[i]拆分成1, 2, 4, ..., 2^k, c其中c是剩余部分这样若干个“物品包”每个包视为一个独立的0/1物品。因为任何数量都可以由这些2的幂次组合而成。这样物品总数从Σs[i]降为Σlog(s[i])再套用0/1背包即可。单调队列优化可以进一步将复杂度优化到O(NV)是更高级的优化国赛有可能考到其思想。实操心得背包问题的变种极多比如求方案数、求具体方案、二维费用背包体积重量、分组背包每组内最多选一个等。核心在于准确理解状态定义和设计正确的转移方程。刷题时建议先彻底搞懂0/1背包的一维写法然后对比理解完全背包的正序原因最后攻克多重背包的二进制拆分。蓝桥杯真题里《包子凑数》就是一个结合了完全背包和数论的好题。4. 线性DP序列与字符串问题的利器线性DP是指状态沿着一个线性维度如序列长度、时间推进的DP。最长上升子序列LIS和最长公共子序列LCS是其代表。4.1 最长上升子序列LIS两种经典解法问题描述给定一个长度为N的数列求数值严格单调递增的子序列的长度最长是多少。解法一朴素DPO(n²)状态定义dp[i]表示以第i个数字结尾的最长上升子序列的长度。转移方程dp[i] max(dp[j]) 1其中0 j i且a[j] a[i]。意思是在i之前找一个结尾比a[i]小的子序列接上a[i]。初始化每个位置至少可以以自己结尾长度为1所以dp[i] 1。答案max(dp[0...n-1])。n len(a) 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 log n)这是竞赛中的标准最优解法必须掌握。维护一个数组tailtail[len]表示长度为len的上升子序列中末尾元素的最小值。这个数组本身是严格递增的。过程遍历每个数x在tail中找到第一个大于等于x的位置pos二分查找。如果pos是当前tail的长度即x比所有末尾都大则x可以接在后面使最长长度1。否则用x替换tail[pos]。因为对于同样长度为pos1的子序列一个更小的末尾值x比原来的tail[pos]“潜力”更大更容易让后面的数接上。答案最终tail数组的长度就是LIS的长度。import bisect tail [] for x in a: pos bisect.bisect_left(tail, x) # 找到第一个 x 的位置 if pos len(tail): tail.append(x) else: tail[pos] x print(len(tail))注意这个方法求出的是长度tail数组本身不一定是一个合法的LIS它只维护了各种长度的最小末尾。如果需要输出具体序列通常还是用O(n²)的DP并记录前驱。4.2 最长公共子序列LCS二维状态设计问题描述给定两个字符串A和B求它们的最长公共子序列不要求连续的长度。状态定义dp[i][j]表示字符串A的前i个字符A[0:i]和字符串B的前j个字符B[0:j]的LCS长度。转移方程如果A[i-1] B[j-1]那么最后一个字符可以匹配dp[i][j] dp[i-1][j-1] 1。如果A[i-1] ! B[j-1]那么最后一个字符不匹配LCS长度取决于“不要A的最后一个字符”或“不要B的最后一个字符”中的最大值即dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始化dp[0][j] dp[i][0] 0表示一个空串与任何串的LCS长度为0。答案dp[len(A)][len(B)]。m, n len(A), len(B) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): 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[m][n])空间优化同样可以优化到一维但需要用一个变量保存dp[i-1][j-1]因为新的dp[j]即dp[i][j]需要它。代码会稍复杂在竞赛中如果内存不紧张直接用二维更清晰。4.3 编辑距离LCS的扩展编辑距离Levenshtein距离是LCS的一个变种操作包括增、删、改。其DP定义与LCS类似dp[i][j]表示将A的前i个字符变成B的前j个字符所需的最少操作次数。转移方程增dp[i][j] dp[i][j-1] 1(在A末尾插入B[j-1])删dp[i][j] dp[i-1][j] 1(删除A[i-1])改dp[i][j] dp[i-1][j-1] (0 if A[i-1]B[j-1] else 1)(如果相同则不改不同则替换一次)dp[i][j]取三者最小值。初始化dp[i][0] i(删i次)dp[0][j] j(增j次)。5. 区间DP与状态机DP处理复杂依赖关系当子问题不是简单的线性顺序而是涉及区间或复杂的状态切换时就需要更高级的DP模型。5.1 区间DP枚举分割点的艺术区间DP常用于处理合并类或回文类问题状态通常定义为dp[l][r]表示区间[l, r]上的最优解或可行性。经典例题石子合并有N堆石子排成一排每次只能合并相邻的两堆代价是两堆石子数之和。求将所有石子合并成一堆的最小总代价。状态定义dp[l][r]表示将区间[l, r]内的所有石子合并成一堆的最小代价。转移方程考虑最后一次合并它一定是将[l, r]分成的左右两堆[l, k]和[k1, r]合并起来。所以我们需要枚举这个分割点k。dp[l][r] min(dp[l][k] dp[k1][r]) sum[l][r], 其中l k r。 这里sum[l][r]是区间[l, r]的石子总数因为合并左右两堆的代价就是它们的总重量。可以用前缀和快速计算。初始化dp[i][i] 0单堆石子不需要合并。计算顺序这是关键。因为计算大区间[l, r]需要用到它内部的更小区间所以我们必须按区间长度len从小到大的顺序来递推。先算所有长度为2的区间再算长度为3的直到长度为N。答案dp[1][N]。n len(stones) prefix_sum [0] * (n1) for i in range(1, n1): prefix_sum[i] prefix_sum[i-1] stones[i-1] dp [[0]* (n1) for _ in range(n1)] # 初始化已在创建时完成全0dp[i][i]0 for length in range(2, n1): # 枚举区间长度 for l in range(1, n-length2): # 枚举左端点 r l length - 1 dp[l][r] float(inf) # 初始化为无穷大 sum_lr prefix_sum[r] - prefix_sum[l-1] for k in range(l, r): # 枚举分割点 dp[l][r] min(dp[l][r], dp[l][k] dp[k1][r] sum_lr) print(dp[1][n])时间复杂度O(n³)。有一个叫“四边形不等式”的优化可以降到O(n²)但国赛中能写出O(n³)通常足够。5.2 状态机DP描述“状态”的流转有些问题中一个对象有多个不同的“状态”决策会影响状态的转移。用状态机模型来设计DP会非常清晰。经典例题股票买卖系列含冷冻期题目你可以进行多次交易买卖为一笔交易但卖出股票后有一天的冷冻期不能第二天买入。求最大利润。状态定义每天结束时我们可能处于三种状态之一dp[i][0]: 第i天结束时持有股票的最大利润。dp[i][1]: 第i天结束时不持有股票且处于冷冻期即今天卖出了股票的最大利润。dp[i][2]: 第i天结束时不持有股票且不处于冷冻期的最大利润。状态转移dp[i][0]今天持有股票可能是昨天就持有(dp[i-1][0])也可能是今天刚买入。今天买入的前提是昨天不持有且不处于冷冻期(dp[i-1][2])。所以dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i])。dp[i][1]今天卖出了股票所以昨天必须持有股票。dp[i][1] dp[i-1][0] prices[i]。dp[i][2]今天不持有也不在冷冻期说明昨天也没持有股票。昨天可能处于冷冻期(dp[i-1][1])或非冷冻期(dp[i-1][2])。dp[i][2] max(dp[i-1][1], dp[i-1][2])。初始化dp[0][0] -prices[0](第一天买入)dp[0][1] 0(第一天不可能卖出)dp[0][2] 0(第一天不操作)答案最后一天不可能持有股票持有未卖出是亏损的所以答案是max(dp[n-1][1], dp[n-1][2])。n len(prices) dp [[0]*3 for _ in range(n)] dp[0][0] -prices[0] for i in range(1, n): dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] dp[i-1][0] prices[i] dp[i][2] max(dp[i-1][1], dp[i-1][2]) print(max(dp[n-1][1], dp[n-1][2]))这种建模方式将复杂的条件冷冻期清晰地转化为状态间的转移规则是解决此类问题的利器。6. 树形DP与状压DP应对更复杂的结构6.1 树形DP在树上做选择树形DP通常用递归DFS的方式实现因为树的结构天然适合递归遍历。核心思想是后序遍历先处理所有子树得到子树的信息再结合根节点做出决策。经典例题没有上司的舞会公司有N个人关系是树形结构。每个人有一个快乐值。直接上司和下属不能同时参加舞会。求最大的快乐值之和。状态定义dp[u][0]表示以u为根的子树且u不参加舞会时子树的最大快乐值。dp[u][1]表示u参加舞会时子树的最大快乐值。转移方程如果u不参加(dp[u][0])那么它的子节点v可以参加也可以不参加我们取最大值累加dp[u][0] max(dp[v][0], dp[v][1])。如果u参加(dp[u][1])那么它的子节点v一定不能参加dp[u][1] dp[v][0]。 最后dp[u][1]还要加上u自己的快乐值。初始化对于叶子节点dp[leaf][0]0,dp[leaf][1]happy[leaf]。计算顺序通过DFS从叶子节点向上递推。答案max(dp[root][0], dp[root][1])。import sys sys.setrecursionlimit(100000) # 防止递归深度过大 def dfs(u): dp[u][1] happy[u] # 初始化选择u的快乐值 for v in children[u]: dfs(v) # 先处理子树 dp[u][0] max(dp[v][0], dp[v][1]) dp[u][1] dp[v][0] # 假设已建好树结构children找到根节点root dfs(root) print(max(dp[root][0], dp[root][1]))6.2 状压DP用二进制表示集合状态当问题的规模较小通常n 20并且涉及“选择”或“排列”时可以用一个整数的二进制位来表示一个集合进行状态压缩。经典例题旅行商问题TSP的DP解法有n个城市给出任意两城市间的距离。从城市0出发每个城市访问一次后回到0求最短路径。状态定义dp[S][i]表示已经访问过的城市集合为S二进制状态压缩并且当前位于城市i的最短路径长度。例如S1011(二进制)表示城市0,1,3已访问。转移方程考虑当前状态(S, i)下一步要去一个还没去过的城市j。则dp[S|(1j)][j] min(dp[S|(1j)][j], dp[S][i] dist[i][j])。初始化dp[1][0] 0表示从城市0出发只访问了城市0当前在0距离为0。其他状态初始化为无穷大。计算顺序按集合S的大小即已访问城市数量从小到大递推。答案访问完所有城市后再回到0。即min(dp[(1n)-1][i] dist[i][0])对所有i取最小值。n 4 dist [[0,2,6,5],[2,0,4,4],[6,4,0,2],[5,4,2,0]] # 示例距离矩阵 INF float(inf) dp [[INF]*n for _ in range(1n)] dp[1][0] 0 # 从0号城市出发 for S in range(1n): # 遍历所有状态 for i in range(n): if dp[S][i] INF: # 状态不可达 continue if not (S i) 1: # 当前城市i不在集合S中理论上不会发生但检查一下 continue for j in range(n): if (S j) 1: # 城市j已经访问过 continue new_S S | (1 j) dp[new_S][j] min(dp[new_S][j], dp[S][i] dist[i][j]) ans INF for i in range(n): ans min(ans, dp[(1n)-1][i] dist[i][0]) print(ans)状压DP的难点在于对二进制操作要非常熟练并且要能设计出合理的状态表示。7. 国赛真题实战分析与避坑指南动态规划在蓝桥杯国赛中几乎每年必考且常作为压轴题或难题出现。下面结合常见考点和我的踩坑经验总结几点实战要点。7.1 识别DP问题的特征拿到题目如何快速判断可能是DP求最值最大/最小数量、最大/最小代价、最长/最短长度等。计数问题求方案总数、路径数等且通常有取模要求。可行性问题问“是否可能”、“能否达成”。数据范围暗示n在10^2到10^3级别可能对应O(n²)或O(n³)的DPn在20左右可能对应状压DP O(n2^n)。问题具有重叠子问题暴力搜索会重复计算很多相同情况。问题具有最优子结构大问题的最优解可以由小问题的最优解推导出来。7.2 状态设计是灵魂初始化是根基状态设计宁多勿少在时间空间允许的情况下多开一维状态让转移更清晰远比为了省空间而设计一个晦涩的状态要好。比如处理“恰好”vs“不超过”的问题多一维状态可能更直观。初始化要小心特别是求最小值时通常初始化为一个很大的数如float(inf)但起点状态要初始化为0或合法值。求“恰好”装满背包的方案数时dp[0]1其他dp[j]0。注意下标偏移题目给的索引从0开始还是1开始dp数组通常从0或1开始要统一避免IndexError。我个人的习惯是在输入时就把数据读到下标1开始的位置这样思维上更连贯。7.3 调试与对拍技巧DP代码写出来如果样例没过或者感觉不对怎么调试打印DP表对于二维DP把整个dp数组打印出来与手算的小规模样例对比。这是最直接有效的方法。缩小数据规模自己构造一个n3或4的极小样例手动模拟整个过程再与程序输出对比。对拍写一个绝对正确但很慢的暴力搜索DFS程序用于小数据范围n15的随机测试。生成随机输入分别运行DP程序和暴力程序对比结果。这是竞赛中验证算法正确性的黄金标准。关注边界检查i0,j0,S0这些边界状态是否正确初始化转移时是否越界。7.4 时间与空间复杂度的权衡空间优化在确定一维优化正确无误后再进行。国赛环境通常宽松如果没把握用二维数组更稳妥。剪枝在DP循环中如果某些状态明显不可能转移到最终答案可以提前continue。例如在背包问题中内层循环可以从v[i]开始而不是从0开始。避免不必要的计算比如区间DP中前缀和可以预处理不要在循环里重复求和。动态规划的学习没有捷径就是“理解模型 - 刷经典题 - 总结归纳 - 挑战变形题”的循环。国赛在即建议你把本文提到的每个经典模型都去找2-3道蓝桥杯真题或高质量练习题巩固。写代码时先自己思考状态设计和转移方程卡住了再看题解这样收获最大。记住在考场上一个清晰的、哪怕不是最优的DP思路也比一个模糊的“贪心”猜想更有机会得分。祝你备赛顺利国赛夺魁