1. 项目概述为什么动态规划是蓝桥杯国赛的“胜负手”如果你正在备战蓝桥杯国赛尤其是到了最后冲刺阶段那么“动态规划”这四个字绝对是你绕不开、也绝不能轻视的核心高地。我参加过多次竞赛也带过不少学生一个非常直观的感受是国赛级别的题目尤其是压轴题动态规划出现的频率和难度往往是决定最终排名的关键。它不像一些语法题或者简单的模拟题会就是会不会也能蒙个几分。动态规划题目思路对了代码可能简洁优雅轻松拿满分思路卡壳或者对状态定义理解有偏差那很可能就是零分。所以把这个专题吃透其战略意义不亚于为你的竞赛之旅装上了一个“稳定器”。简单来说动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它的核心思想是“记住已经求过的解”避免重复计算。在蓝桥杯的语境下这意味着你要面对的是诸如“最长上升子序列”、“01背包问题”、“路径规划”、“区间划分”等一系列经典且多变的模型。这些题目往往数据规模较大暴力搜索必然超时而动态规划提供了一条高效、可行的解题路径。备战这个专题目标非常明确第一识别题目中的动态规划特征第二熟练运用几种经典模型第三掌握状态设计和转移方程推导的技巧第四能处理一些常见的优化和变形。这不仅是应对国赛更是对你算法思维的一次深度锤炼。2. 核心思路拆解动态规划的“灵魂三步曲”很多同学一听到动态规划就觉得头大感觉状态转移方程像天书。其实只要抓住核心步骤它是有章可循的。我个人习惯将其总结为“灵魂三步曲”无论是面对“最长上升子序列”还是复杂的“蓝桥杯真题”都按这个框架来思考。2.1 第一步定义状态——明确“我们到底要记录什么”这是最关键也最容易出错的一步。状态定义直接决定了后续转移方程能否顺利写出以及算法的复杂度。状态通常用一个数组dp数组来表示dp[i]或者dp[i][j]的含义必须清晰、无歧义。经典例子1最长上升子序列 (LIS)状态定义dp[i]表示以第 i 个数字结尾的最长上升子序列的长度。为什么这么定义因为子序列的“结尾”是一个很好的划分点。如果我们知道了所有以更早位置结尾的LIS长度那么要计算dp[i]只需要看看前面哪些数字比nums[i]小然后接在它们后面即可。如果定义为“前i个数字中的LIS长度”转移起来会非常困难因为你不知道这个LIS是否以第i个数字结尾。实操心得定义状态时多问自己一句“这个状态是否包含了解决问题所需的全部信息并且能方便地从更小的状态推导过来” 像“以...结尾”、“考虑到...位置为止”是常见的切入点。经典例子201背包问题状态定义dp[i][j]表示从前 i 个物品中选取总容量不超过 j 时能获得的最大价值。为什么是二维因为限制条件有两个维度物品的个数和背包的容量。我们需要同时记录这两个维度的信息才能进行决策对于第i个物品是选还是不选。注意事项蓝桥杯国赛的背包问题往往不会直接告诉你这是背包可能会伪装成资源分配、方案计数等问题。关键在于识别出“有若干物品或选择每个有消耗重量/成本和收益价值在总消耗有限制的情况下求最大收益或方案数”这个核心模型。2.2 第二步推导状态转移方程——找到“如何从已知推未知”的公式状态定义好后就要找出dp[i]或dp[i][j]与之前状态的关系。这是动态规划的核心逻辑。对于LISdp[i] max(dp[j]) 1其中0 j i且nums[j] nums[i]。解读要计算以i结尾的LIS就遍历i之前的所有位置j。如果nums[j]比nums[i]小说明nums[i]可以接在以j结尾的LIS后面形成一个更长的序列。我们取所有可能接上的序列中长度最长的那个然后加1加上nums[i]自己。时间复杂度直观实现是 O(n²)对于 n10^3 量级的数据是安全的。国赛有时会卡 O(n²)需要更优的 O(n log n) 的贪心二分查找方法这点后面会提。对于01背包对于每个物品i和每种容量j我们有两种选择不选第 i 个物品那么最大价值就是dp[i-1][j]即只看前 i-1 个物品容量为 j 时的最优解。选第 i 个物品前提是背包容量j weight[i]。如果选了那么剩余容量为j - weight[i]我们需要在前 i-1 个物品中寻找这个剩余容量下的最优解即dp[i-1][j-weight[i]]然后加上当前物品的价值value[i]。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。空间优化滚动数组仔细观察方程dp[i]这一层只依赖于dp[i-1]这一层。因此我们可以只用一维数组dp[j]但需要从后往前遍历j从最大容量到当前物品重量以确保在计算dp[j]时dp[j-weight[i]]还是上一轮i-1的值没有被本轮覆盖。这是背包问题必须掌握的优化技巧。2.3 第三步确定边界与计算顺序——打好“地基”规划“施工顺序”边界初始化这是最容易忽略导致WAWrong Answer的地方。LIS通常将dp数组初始化为1因为每个数字本身至少可以构成一个长度为1的上升子序列。01背包通常将dp[0][...]和dp[...][0]初始化为0。表示没有物品时价值为0容量为0时价值也为0。特别提醒对于求“方案数”的动态规划边界往往非常关键。例如dp[0]可能代表一种空方案需要初始化为1。计算顺序大多数动态规划都是“自底向上”的填表过程。我们需要确保在计算一个状态时它所依赖的子状态都已经被计算出来了。LISdp[i]依赖于所有j i的dp[j]所以i从 0 到 n-1 顺序遍历即可。01背包二维i和j通常都采用顺序遍历。01背包一维优化后i顺序遍历物品j必须逆序遍历容量。注意这三步不是孤立的而是循环往复、不断调整的过程。有时初步定义的状态可能无法写出简洁的转移方程这时就需要回头重新思考状态的定义是否合理。多练习经典模型是培养这种“感觉”的最佳途径。3. 经典模型深度剖析与国赛真题链接掌握了基本步骤我们来看看蓝桥杯国赛最青睐的几个动态规划模型并结合真题或类似题型进行分析。3.1 线性动态规划最长上升子序列及其优化线性DP是基础LIS是代表。除了标准的 O(n²) 解法国赛更可能考察其 O(n log n) 的优化解法因为这能处理 n10^5 甚至更大的数据。O(n log n) 解法核心维护一个tails数组tails[k]表示长度为 k1 的所有上升子序列中结尾元素的最小值。这个数组本身是严格递增的。操作遍历每个数字x在tails数组中用二分查找找到第一个大于等于x的位置pos。如果pos等于当前tails的长度说明x比所有结尾都大可以接在后面形成更长的序列于是将x添加到tails末尾。否则用x替换tails[pos]。因为对于长度为pos1的子序列用一个更小的结尾值x替换掉tails[pos]未来更有潜力接上更大的数。最终结果tails数组的长度就是最长上升子序列的长度。国赛链接思考这种思想可以变种。例如题目可能不是求“最长上升”而是求“最长不降”那么二分查找的就是第一个“大于”x的位置。也可能将数字替换为某种复杂的结构但核心的“维护有序序列二分查找”思想不变。3.2 背包问题家族从01背包到多重背包背包问题是动态规划的“军火库”变种极多。01背包每个物品最多选一次。前面已详细说明。完全背包每个物品可以选无限次。状态转移方程二维dp[i][j] max(dp[i-1][j], dp[i][j-weight[i]] value[i])。注意第二项是dp[i][j-weight[i]]而不是dp[i-1][j-weight[i]]这是因为物品 i 可以被重复选取。一维优化只需将01背包的一维逆序遍历j改为正序遍历j即可。因为正序允许同一物品被多次使用。多重背包每个物品有固定的数量限制s[i]。朴素解法将其视为 s[i] 个相同的01背包物品但复杂度高。二进制优化这是国赛考点。将数量s拆分成 1, 2, 4, ..., 2^k, c其中 c s - (2^{k1}-1)这样几个“物品包”。这些“物品包”通过组合可以表示出 0~s 之间的任意数量。这样就将问题转化为了一个物品数量更少的01背包问题。单调队列优化更高级的优化在特定数据范围下使用国赛出现过相关思想的题目。国赛真题举例像“资源分配”、“预算方案”、“凑硬币/邮票”等问题背后都是背包模型。例如给定几种面值的硬币每种无限多或有限多问凑出某个金额有多少种组合方式或最少需要多少枚硬币。这就是完全背包或多重背包的方案数或最小值问题。状态定义dp[j]为凑出金额 j 的方案数或最小硬币数转移方程相应调整。3.3 区间动态规划破解“石子合并”与“括号匹配”区间DP通常处理序列或区间上的问题状态定义一般为dp[i][j]表示区间[i, j]上的最优解或可行方案数。经典模型石子合并问题N堆石子排成一排每次只能合并相邻的两堆代价为两堆石子数之和求合并成一堆的最小总代价。状态定义dp[i][j]表示将区间[i, j]内的所有石子合并成一堆的最小代价。状态转移考虑最后一次合并它一定是将[i, j]分成了左右两堆[i, k]和[k1, j]进行合并。所以我们需要枚举这个分界点k。dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j))对于所有i k j。其中sum(i, j)是区间[i, j]的石子总数可以用前缀和快速计算。计算顺序因为大区间[i, j]依赖于更小的区间所以我们需要按区间长度从小到大的顺序来递推。先算所有长度为1的区间代价为0再算长度为2的依此类推。国赛链接区间DP的变体非常多。例如“能量项链”、“多边形划分”、“最长回文子序列”等。关键在于识别出“问题可以分解为对连续子区间/子序列的操作”这一特征。蓝桥杯曾考过的“高僧斗法”虽然更像博弈论但分析过程有区间思想的影子等题目也要求选手具备良好的区间分析能力。3.4 状态压缩动态规划处理“小规模集合”的利器当问题的状态中包含了“是否选择过某个元素”这类集合信息且元素数量较少通常 n 20时可以用一个整数的二进制位来表示这个集合这就是状态压缩DP。经典模型旅行商问题 (TSP)问题访问n个城市编号0~n-1每个城市只去一次最后回到起点求最短路径。状态定义dp[S][i]表示已经访问过的城市集合为S二进制状态并且当前位于城市i的最小花费。状态转移考虑下一步走到一个未访问的城市j。dp[S | (1j)][j] min(dp[S | (1j)][j], dp[S][i] dist[i][j])。初始化dp[10][0] 0表示从城市0出发只访问了城市0花费为0。结果最终答案是min(dp[(1n)-1][i] dist[i][0])表示所有城市都访问完后从某个城市i回到起点0的最小总花费。国赛应用蓝桥杯国赛的压轴题有时会涉及状态压缩。例如在棋盘如n x m但m较小上放置某种形状的棋子要求满足某些约束求方案数。可以用dp[i][state]表示处理到第i行当前行的状态为state时的方案数状态state用二进制表示该行每个格子是否被占据。转移时需要检查state与上一行状态的兼容性。4. 国赛真题实战与举一反三理论说得再多不如真刀真枪分析一道题。我们选取一个具有代表性的问题来拆解。假设题目给定一个长度为 N 的数组数组中可能有正数、负数和零。请找出其中乘积最大的连续子数组并输出这个最大乘积。类似问题在各类竞赛中屡见不鲜是动态规划处理“有负数和零”情况的经典例题4.1 问题分析与状态设计最直观的想法是模仿“最大子数组和”问题定义dp[i]为以i结尾的最大乘积子数组的乘积。但这里有个陷阱负数乘以负数会变成正数。因此仅记录最大值是不够的因为一个很小的负数最小值在遇到另一个负数时可能会“翻身”变成最大值。状态设计maxDp[i]以第i个元素结尾的连续子数组的最大乘积。minDp[i]以第i个元素结尾的连续子数组的最小乘积也就是绝对值最大的负数。为什么需要两个状态因为当前元素nums[i]可能为正也可能为负。如果nums[i] 0那么以i结尾的最大乘积要么是nums[i]自己要么是nums[i] * maxDp[i-1]接在前面的最大乘积子数组后面。最小乘积同理是nums[i]自己或nums[i] * minDp[i-1]。如果nums[i] 0情况就反转了。以i结尾的最大乘积可能是nums[i] * minDp[i-1]当前负数乘以前面的最小负数负负得正。而以i结尾的最小乘积可能是nums[i] * maxDp[i-1]当前负数乘以前面的最大正数得到一个更小的负数。4.2 状态转移方程与实现根据上面的分析我们可以得到转移方程maxDp[i] max(nums[i], nums[i] * maxDp[i-1], nums[i] * minDp[i-1]) minDp[i] min(nums[i], nums[i] * maxDp[i-1], nums[i] * minDp[i-1])同时我们需要一个全局变量ans来记录遍历过程中出现的所有maxDp[i]的最大值。初始化maxDp[0] minDp[0] nums[0],ans nums[0]。代码框架Pythondef maxProduct(nums): n len(nums) if n 0: return 0 max_dp [0] * n min_dp [0] * n max_dp[0] min_dp[0] nums[0] ans nums[0] for i in range(1, n): candidates (nums[i], nums[i] * max_dp[i-1], nums[i] * min_dp[i-1]) max_dp[i] max(candidates) min_dp[i] min(candidates) ans max(ans, max_dp[i]) return ans空间优化同样dp[i]只依赖于dp[i-1]可以用两个变量cur_max,cur_min代替数组。4.3 举一反三从“乘积最大”到“国赛变种”这道题给了我们一个非常重要的启示当状态转移可能因为当前值的正负号发生“反转”时考虑同时维护最大值和最小值两个状态。变种1环形数组的最大乘积子数组。可以将原数组复制一份接到后面但限制子数组长度不超过N。或者更巧妙的方法是最大乘积要么出现在普通数组内用上述方法求要么出现在环形部分即数组头尾相连。环形部分的最大乘积 数组总乘积 / 数组中间某段最小乘积如果这段最小乘积是负数且绝对值很大。但要注意处理0的情况0会使除法失效。通常可以枚举分割点或者将问题转化为“数组总和减去最小子数组和”的思路对于乘积不适用这里只是类比思想。变种2带删除操作的子数组最大和/积。有些题目允许你从子数组中删除至多一个元素。这可以定义状态dp[i][0/1]其中第二维表示是否已经使用过删除机会。dp[i][0]表示以i结尾且没删除过元素的最大值dp[i][1]表示以i结尾且已经删除过一个元素的最大值。转移时dp[i][1]可以从dp[i-1][1] nums[i]之前删过了现在正常加或者dp[i-1][0]之前没删过现在删除nums[i]相当于直接继承前一个状态转移过来。5. 备赛策略与临场技巧最后结合我个人和学生的经验分享一些针对蓝桥杯国赛动态规划专题的备赛策略和考场上的应对技巧。5.1 系统性训练路线图夯实基础1-2周把最长上升子序列O(n²) O(n log n)、01背包/完全背包/多重背包朴素与二进制优化、最大子数组和、爬楼梯/打家劫舍这类最最经典的线性DP和背包问题刷到滚瓜烂熟。做到看到题目描述5分钟内能写出正确代码。攻克核心2-3周重点突破区间DP石子合并、括号匹配和状态压缩DP旅行商、棋盘放置。这些是区分度所在。找专题练习理解状态设计和转移的套路。真题演练与模拟持续进行刷历年蓝桥杯国赛真题中的动态规划题。不要只看AC代码要自己思考我能不能识别出这是DP我的状态定义是什么为什么题解是那样定义的我的转移方程哪里错了这个过程是提升最快的。总结归纳每周进行建立自己的“DP模型笔记本”。记录每种模型的典型问题描述状态定义为什么这样定义转移方程边界条件常见变种易错点5.2 考场上的思维流程与调试技巧识别信号看到题目先看数据范围。如果 n 在 10^3 到 10^4 O(n²) 可能可行如果 n 在 10^5 大概率需要 O(n log n) 或 O(n)如果 n 很小如 20但问题看起来需要枚举子集考虑状态压缩。题目中出现“最大/最小”、“方案数”、“能否达成”等关键词且暴力搜索明显不行时优先考虑DP。手推样例不要一上来就敲代码。用题目给的小样例甚至自己构造更简单的样例在纸上手动模拟你的DP过程。验证你的状态定义和转移方程是否正确。这是避免思路跑偏最有效的方法。先写朴素再优化如果对优化没把握比如滚动数组先写出二维的、逻辑清晰的朴素DP版本。确保正确后再考虑空间优化。在时间紧迫的考场上正确性远比那一点空间开销重要。调试利器打印DP表如果程序结果不对别干瞪眼。把关键的DP数组尤其是前几行打印出来和你手推的结果对比。很容易就能发现是初始化错了还是转移方程写错了或者是循环范围有问题。注意数据溢出蓝桥杯的题目有时会故意设置一些导致int溢出的数据。对于涉及累加、累乘的DP特别是求方案数可能很大的情况长期开long long是一个好习惯。检查题目要求的取模操作一定不要漏。动态规划的学习曲线确实比较陡峭但一旦跨过那个“开窍”的点你会发现很多难题都变得有迹可循。国赛在即围绕这几个核心模型进行深度练习和总结比你漫无目的地刷一百道题要有效得多。记住理解永远比记忆重要多问“为什么这样定义状态”多动手推导你的DP能力一定会成为你在赛场上最可靠的武器。