1. 项目概述一份来自国赛战场的动态规划“兵器谱”如果你正在备战蓝桥杯国赛或者任何需要用到动态规划DP的算法竞赛那么你大概率和我一样经历过面对复杂状态转移方程时的迷茫以及调试边界条件时的抓狂。DP这个被誉为算法竞赛“分水岭”的题型其核心魅力在于将复杂问题分解为重叠子问题并通过记忆化或递推来高效求解。然而它的难点也恰恰在此——状态定义千变万化转移方程构思精巧稍有不慎便会陷入“想不出来”或“写不出来”的困境。这份“第十二届_国赛蓝桥杯个人模板_DP篇”正是我在多次实战尤其是经历国赛级别的锤炼后整理归纳出的一套核心DP模板与解题框架。它不是一个简单的代码合集而是一套经过验证的“思维兵器谱”和“代码脚手架”。其核心价值在于将常见的DP模型抽象化、模板化让你在面对新题时能快速识别问题本质套用或适配已有框架从而把宝贵的比赛时间用在思考关键的状态设计上而非重复编写基础代码逻辑。无论是刚接触DP的新手还是希望提升解题稳定性的老手这套模板都能提供清晰的路径和可靠的参考。2. DP核心思想与模板设计哲学2.1 动态规划的本质状态、决策与最优子结构动态规划之所以强大是因为它基于一个看似简单却威力巨大的思想利用过去的结果来推导现在。要理解模板首先要吃透这三个核心概念状态State这是描述问题在某个“时刻”或“阶段”情况的变量集合。例如在背包问题中“当前考虑到第i件物品且背包容量剩余j”就是一个状态通常用dp[i][j]表示。设计状态是DP最关键的步骤好的状态应该能唯一确定一个子问题且包含推导后续状态所需的全部信息。决策Decision/Choice在每个状态我们可以做出的选择。例如对于第i件物品决策就是“放入背包”或“不放入背包”。决策会导致状态发生转移。状态转移方程State Transition Equation这是DP的灵魂它定量地描述了如何从已知状态通常是更小的、已解决的状态通过决策推导出当前状态的值。其形式通常为dp[新状态] 最优/聚合(dp[旧状态1], dp[旧状态2], ...)。模板的设计就是针对某一类具有相同状态定义方式和转移逻辑的问题预先将它们的框架搭建好。我们模板库的哲学是覆盖经典模型抽象公共模式提供清晰注释。这样在比赛中你可以像查手册一样快速找到对应模型的骨架然后专注于将具体问题“映射”到这个骨架上。2.2 模板的通用结构与编码规范为了确保模板的清晰性和可用性所有模板都遵循统一的编码结构和注释规范// 模板示例结构 #include bits/stdc.h using namespace std; /** * 模板名称经典01背包问题 * 问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移方程dp[j] max(dp[j], dp[j - v[i]] w[i]) (注意j的遍历顺序) * 复杂度O(N * V) * 注意事项内层循环必须逆序遍历容量以确保每件物品最多被选取一次。 */ void zeroOneKnapSackTemplate() { int N, V; // 物品数量背包容量 cin N V; vectorint v(N 1), w(N 1); // 体积价值。下标从1开始 for (int i 1; i N; i) cin v[i] w[i]; vectorint dp(V 1, 0); // dp数组初始化通常求最大值初始化为0 // 核心递推过程 for (int i 1; i N; i) { // 枚举物品 for (int j V; j v[i]; --j) { // 逆序枚举容量这是01背包的关键 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[V] endl; }注意注释中明确指出了“逆序遍历”这一关键细节和原因。这是模板的精华所在避免使用者因记忆模糊而犯错。3. 经典DP模型模板详解与实战映射3.1 线性DP最长上升子序列LIS及其变种线性DP是基础其状态通常与序列的“位置”线性相关。最长上升子序列LIS是典例。3.1.1 标准O(n²)模板适用于数据规模较小n ≤ 5000的情况思路直观是理解LIS本质的起点。/** * 模板最长上升子序列 (O(n^2)) * 状态定义dp[i] 表示以第i个元素结尾的最长上升子序列长度。 * 转移方程dp[i] max(dp[j]) 1, 对于所有 j i 且 a[j] a[i] * 初始化dp[i] 1 (每个元素自身构成长度为1的子序列) * 结果max(dp[1...n]) */ int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }3.1.2 贪心二分O(n log n)优化模板这是必须掌握的优化版本能处理n高达10^5的情况。其核心是维护一个“潜力序列”d[]d[i]表示长度为i的上升子序列末尾元素的最小可能值。/** * 模板最长上升子序列 (O(n log n)) * 核心维护数组dd[len] x 表示长度为len的LIS的末尾元素最小值为x。 * 流程遍历原数组用二分查找在d中找到第一个大于等于当前元素a[i]的位置pos。 * 如果pos是新的长度即d[pos]未定义或更大则更新d[pos] a[i]。 * 否则用a[i]更新d[pos]因为它为未来更长的子序列提供了更小的末尾值。 * 结果d中被有效更新的最大下标即为LIS长度。 */ int lengthOfLIS_Optimized(vectorint nums) { int n nums.size(); vectorint d; // 潜力数组 d.push_back(nums[0]); for (int i 1; i n; i) { if (nums[i] d.back()) { d.push_back(nums[i]); // 可以延长LIS } else { // 二分查找找到第一个大于等于nums[i]的位置将其替换 auto it lower_bound(d.begin(), d.end(), nums[i]); *it nums[i]; } } return d.size(); // d的长度就是LIS的长度 }实操心得很多变种问题如“最长不下降子序列”、“使序列严格递增的最小修改次数”等都可以基于此模板调整二分比较条件将改为或将lower_bound改为upper_bound。关键在于理解d数组的含义——它维护的是每种长度下最小的末尾值这个“最小”是贪心优化的核心。3.2 背包DP从01背包到分组背包背包问题是DP的“必修课”国赛中常以各种变体出现。3.2.1 01背包ZeroOne Pack上面已给出模板核心是逆序枚举容量确保物品最多选一次。3.2.2 完全背包Complete Pack与01背包的唯一区别是每件物品有无限个。代码上的区别仅仅是正序枚举容量。/** * 模板完全背包问题 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移方程dp[j] max(dp[j], dp[j - v[i]] w[i]) * 关键区别内层对容量的循环是正序j从v[i]到V。因为正序允许在考虑第i件物品时dp[j - v[i]]可能已经包含了第i件物品从而实现无限选取。 */ void completeKnapSackTemplate() { int N, V; cin N V; vectorint v(N1), w(N1); for(int i1; iN; i) cin v[i] w[i]; vectorint dp(V1, 0); for(int i1; iN; i){ for(int jv[i]; jV; j){ // 正序正序正序 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[V] endl; }3.2.3 多重背包Multiple Pack每件物品有固定的数量限制s[i]。朴素解法是将其拆分为s[i]个01背包物品但复杂度高。二进制优化是必须掌握的技巧能将复杂度从O(V * Σs[i])降至O(V * Σlog s[i])。/** * 模板多重背包二进制优化 * 思想将数量为s的物品拆分成1, 2, 4, ..., 2^k, c (c s - (2^{k1}-1)) 这些“新物品”。 * 这些新物品的组合可以表示出0~s之间的任意数量且新物品的数量是log s级别的。 * 然后对这些新物品做01背包即可。 */ void multipleKnapSackBinaryOpt() { int N, V; cin N V; vectorint dp(V 1, 0); vectorpairint, int goods; // 存放体积价值 for (int i 0; i N; i) { int v, w, s; cin v w s; // 二进制拆分 for (int k 1; k s; k * 2) { goods.push_back({v * k, w * k}); s - k; } if (s 0) goods.push_back({v * s, w * s}); } // 对拆分后的goods进行01背包 for (auto [vol, val] : goods) { for (int j V; j vol; --j) { dp[j] max(dp[j], dp[j - vol] val); } } cout dp[V] endl; }3.2.4 分组背包Group Pack物品被分为若干组每组内物品互斥最多选一件。这是许多实际问题的模型如课程选修。/** * 模板分组背包 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移逻辑最外层循环枚举物品组中层循环逆序枚举容量保证每组内最多选一个最内层循环枚举组内物品。 * 核心对于每个容量j我们是在所有组内物品中选一个最优的或不选。 */ void groupKnapSackTemplate() { int N, V; // N组物品背包容量V cin N V; vectorint dp(V 1, 0); for (int i 0; i N; i) { // 枚举组 int s; // 本组物品数量 cin s; vectorint v(s), w(s); for (int k 0; k s; k) cin v[k] w[k]; // 注意容量循环必须在最内层物品循环的外面且逆序 for (int j V; j 0; --j) { // 枚举容量 for (int k 0; k s; k) { // 枚举组内物品 if (j v[k]) { dp[j] max(dp[j], dp[j - v[k]] w[k]); } } } } cout dp[V] endl; }注意事项分组背包的循环顺序是易错点。必须先容量后物品且容量要逆序。可以这样理解对于当前组我们把dp[j]看作一个“临时状态”在枚举组内所有物品的过程中用它们来更新dp[j]而逆序保证了更新dp[j]时用到的dp[j - v[k]]是上一组或更早的状态不会发生本组物品被重复选取。3.3 区间DP枚举分割点的艺术区间DP用于解决涉及区间合并、分割的问题如石子合并、括号匹配等。其状态通常定义为dp[i][j]表示区间[i, j]上的最优解。3.3.1 经典模板石子合并最小代价/** * 模板区间DP - 石子合并最小代价 * 状态定义dp[i][j] 表示合并第i堆到第j堆石子的最小代价。 * 转移方程dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j]), 其中 i k j。 * sum[i][j]是区间[i,j]的石子总重量可以用前缀和快速计算。 * 初始化dp[i][i] 0 (单堆石子无需合并) * 遍历顺序由于计算dp[i][j]需要用到更短的区间结果所以需要按区间长度len从小到大遍历。 */ int stoneMergeMinCost(vectorint stones) { int n stones.size(); vectorint prefix(n 1, 0); for (int i 1; i n; i) prefix[i] prefix[i - 1] stones[i - 1]; vectorvectorint dp(n, vectorint(n, 0)); // 按区间长度遍历 for (int len 2; len n; len) { // len1时代价为0已初始化 for (int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] INT_MAX; // 初始化为无穷大 int sum_ij prefix[j 1] - prefix[i]; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] sum_ij); } } } return dp[0][n - 1]; }3.3.2 区间DP的遍历顺序与优化理解遍历顺序至关重要。必须保证在计算dp[i][j]时其依赖的所有更小区间dp[i][k]和dp[k1][j]都已被计算出来。按长度递增遍历是通用且安全的方法。 对于某些问题如平行四边形优化可以进一步优化内层k的枚举范围但国赛中掌握基础模板已足够应对大部分题目。3.4 状态压缩DP状压DP用比特位表示集合状压DP常用于处理小规模n ≤ 20的集合选择问题如旅行商问题TSP、棋盘覆盖、任务安排等。其核心是用一个整数的二进制位来表示一个集合第i位为1表示元素i在集合中。3.4.1 经典模板旅行商问题TSP/** * 模板状态压缩DP - 旅行商问题TSP * 问题从城市0出发访问所有城市恰好一次后回到0求最短路径。 * 状态定义dp[S][i] 表示已经访问过的城市集合为S二进制表示且当前位于城市i的最小花费。 * 转移方程dp[S][i] min(dp[S\{i}][j] dist[j][i]), 其中 j 属于集合 S\{i}。 * 初始化dp[10][0] 0表示从城市0出发只访问了城市0花费为0。 * 结果min(dp[(1n)-1][i] dist[i][0])即访问完所有城市后从最后所在城市i返回0的总花费。 */ int tsp(vectorvectorint dist) { int n dist.size(); int state_num 1 n; vectorvectorint dp(state_num, vectorint(n, INT_MAX / 2)); // 防止加法溢出 dp[1][0] 0; // 起点在0状态为只包含0 for (int S 1; S state_num; S) { // 枚举所有状态 for (int i 0; i n; i) { if (!(S i 1)) continue; // 状态S中必须包含i if (dp[S][i] INT_MAX / 2) continue; // 无效状态 // 尝试从状态S中从i转移到下一个未访问的城市j for (int j 0; j n; j) { if (S j 1) continue; // j不能在S中未访问 int next_S S | (1 j); dp[next_S][j] min(dp[next_S][j], dp[S][i] dist[i][j]); } } } int ans INT_MAX; int full_state (1 n) - 1; for (int i 1; i n; i) { // 从任意非0城市i返回0 if (dp[full_state][i] INT_MAX / 2) { ans min(ans, dp[full_state][i] dist[i][0]); } } return ans; }实操心得状压DP的难点在于对二进制操作要非常熟练。常用操作有S (1 i)判断元素i是否在集合S中。S | (1 i)将元素i加入集合S。S ~(1 i)将元素i从集合S中移除。for(int sub S; sub; sub (sub-1) S)枚举集合S的所有非空子集。这个技巧在需要枚举子集进行转移时非常有用。3.5 数位DP统计数字区间内的特定数数位DP用于解决与数字的数位相关的问题例如统计区间[L, R]内有多少个数满足某些性质如不含数字4、是回文数、各位数字之和等。其核心是记忆化搜索DFS按位处理并利用“是否达到上限is_limit”和“前导零is_num”等状态来剪枝。3.5.1 通用模板框架/** * 模板数位DP通用框架记忆化搜索 * 问题求区间[0, num]内满足条件P的数字个数。 * 状态定义dp[pos][state][is_limit][is_num] * - pos: 当前正在处理第几位从高位到低位。 * - state: 一个与题目条件相关的状态如前面数字的和、前面数字的模数、是否包含某数字等。 * - is_limit: 当前位是否受到num对应位的限制。若为true则当前位最大只能取s[pos]否则可取0-9。 * - is_num: 当前位之前是否已经填过数字即是否跳过了前导零。用于处理前导零不影响状态的情况。 * 返回值从pos位开始在给定状态下能构造出的满足条件的数字个数。 */ class DigitDP { string s; // 将上界num转为字符串方便按位处理 vectorvectorvectorvectorint dp; // 记忆化数组维度根据state定义 // 根据具体问题定义state的维度和初始值 public: int solve(int num) { s to_string(num); int n s.length(); // 初始化dp为-1表示未计算。维度[pos][state_dim1][state_dim2][2][2] dp.assign(n, vector...(..., -1)); // 此处根据具体state定义 // 从最高位开始搜索起始状态位置0初始state受上限限制尚未开始填数is_numfalse return dfs(0, init_state, true, false); } int dfs(int pos, int state, bool is_limit, bool is_num) { if (pos s.size()) { // 递归终点所有位处理完毕 return is_num ? 1 : 0; // 如果是一个有效的数字至少填了一位返回1否则返回0处理全0情况 } // 记忆化如果不受限制且已经是一个有效数字且状态已计算过直接返回 if (!is_limit is_num dp[pos][state] ! -1) { return dp[pos][state]; } int res 0; int up is_limit ? s[pos] - 0 : 9; // 当前位能取的最大值 // 如果之前一直没填数可以选择继续跳过填0但这不是一个有效数字位 if (!is_num) { res dfs(pos 1, state, false, false); // 跳过is_limit变为false因为前导0不受原数限制 } // 枚举当前位可以填的数字 int start is_num ? 0 : 1; // 如果之前没填过数不能填0否则还是前导零 for (int d start; d up; d) { if (!isValid(d, state)) continue; // 根据题目条件判断当前数字d是否合法 int next_state getNextState(state, d); // 根据当前状态和数字d计算下一个状态 res dfs(pos 1, next_state, is_limit (d up), true); } // 记录状态只有当不受限制且是有效数字时才记录因为受限制的状态是唯一的不需要记忆化 if (!is_limit is_num) { dp[pos][state] res; } return res; } // 以下两个函数需要根据具体问题实现 bool isValid(int digit, int state) { // 判断在当前state下digit是否允许被填入 // 例如不能填4或不能连续填两个1等 return true; // 示例 } int getNextState(int old_state, int digit) { // 根据旧状态和填入的数字计算新状态 // 例如新状态为各位数字之和则返回 old_state digit return old_state; // 示例 } };注意事项数位DP的模板看似复杂但结构固定。关键在于根据题目定义state以及实现isValid和getNextState函数。is_limit和is_num是两个核心的剪枝和状态区分标志务必理解其作用。处理区间[L, R]的问题时通常转化为solve(R) - solve(L-1)。4. 国赛真题中的DP实战分析与模板应用理论需要结合实战。我们选取几道经典的蓝桥杯国赛DP真题看看如何将问题抽象并套用或修改上述模板。4.1 真题解析一矩阵中的最大权值路径线性DP变种问题简述给定一个N x M的矩阵每个格子有分值。从左上角走到右下角每次只能向右或向下求路径最大分值之和。模板映射这是最基础的二维线性DP状态dp[i][j]表示走到(i, j)格子的最大分值。转移方程dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]初始化dp[0][0] grid[0][0]第一行和第一列需要单独初始化因为只能从一个方向来。代码实现几乎可以直接套用线性DP的思路注意边界处理。int maxPathSum(vectorvectorint grid) { int n grid.size(), m grid[0].size(); vectorvectorint dp(n, vectorint(m, 0)); dp[0][0] grid[0][0]; for (int i 1; i n; i) dp[i][0] dp[i-1][0] grid[i][0]; for (int j 1; j m; j) dp[0][j] dp[0][j-1] grid[0][j]; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } return dp[n-1][m-1]; }4.2 真题解析二带限制的整数划分背包DP变种问题简述将整数N划分成若干个正整数之和且每个正整数不超过M求划分方案数。例如N5, M3划分有11111, 1112, 113, 122, 23。模板映射这可以看作是一个完全背包问题。背包容量是N物品是1, 2, ..., M每个物品可以无限取因为一个数字可以重复出现求恰好装满背包的方案数。状态定义dp[j]表示凑成总和为j的方案数。转移方程dp[j] dp[j - i]其中i是物品数字大小从1到M。初始化dp[0] 1凑成0的方案数为1即什么都不选。代码实现注意这是求方案数所以是累加。int partitionNumber(int N, int M) { vectorint dp(N 1, 0); dp[0] 1; for (int i 1; i M; i) { // 枚举“物品”数字i for (int j i; j N; j) { // 完全背包正序枚举容量 dp[j] dp[j - i]; } } return dp[N]; }4.3 真题解析三复杂状态转移的区间DP问题简述给定一个字符串添加最少的字符使其成为回文串。求最少添加字符数。模板映射这是一个区间DP问题。状态dp[i][j]表示将子串s[i...j]变成回文串所需的最少添加次数。转移分析如果s[i] s[j]那么两端字符已经配对问题转化为dp[i1][j-1]。如果s[i] ! s[j]那么可以在左边添加一个s[j]或者在右边添加一个s[i]。即dp[i][j] min(dp[i1][j], dp[i][j-1]) 1。初始化单个字符本身就是回文dp[i][i] 0。相邻字符如果相等则为0否则为1。代码实现按区间长度递增遍历。int minAddToPalindrome(string s) { int n s.length(); vectorvectorint dp(n, vectorint(n, 0)); for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { dp[i][j] (len 2) ? 0 : dp[i 1][j - 1]; } else { dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1; } } } return dp[0][n - 1]; }5. 模板使用心法与调试技巧5.1 如何选择与修改模板识别问题类型首先判断问题属于哪一大类线性、背包、区间、状压、树形、数位等。看数据范围是重要线索n≤20可能是状压n≤100可能是区间或普通DP涉及“选或不选”和“容量”可能是背包。定义状态这是最关键的一步。问自己需要哪些信息才能唯一确定一个子问题并且能推导出后续状态状态维度可能是一维位置、二维位置状态、甚至更多。推导转移方程思考从哪些已知状态能转移到当前状态。写出方程后务必检查边界条件和初始化。确定遍历顺序确保在计算dp[x]时它所依赖的状态都已经被计算过。对于线性DP通常顺序遍历对于区间DP按长度遍历对于背包注意01背包逆序、完全背包正序。适配模板将你定义的状态和方程套入最相近的模板框架中。例如如果你的问题是一个变种的背包就基于01背包或完全背包的模板进行修改。5.2 调试DP程序的常见“坑点”数组越界这是最常见的运行时错误。特别是在处理dp[i-1],dp[i-v]时一定要确保下标大于等于0。在竞赛中可以将dp数组大小稍微开大一点例如5或10并从下标1开始使用可以避免很多边界麻烦。初始化错误求最大值/最小值通常初始化为负无穷/正无穷但dp[0]或起点状态需要根据题意设为0或其他特定值。求方案数通常dp[0] 1其他初始为0。务必仔细考虑所有边界状态的初始值。遍历顺序错误尤其是背包问题。牢记01背包逆序完全背包正序分组背包先容量后物品且逆序。可以这样记忆“逆序保证唯一性正序允许无限性”。状态转移方程逻辑错误这是最隐蔽的错误。建议打印DP表对于小规模样例将整个dp数组打印出来与手动计算的结果对比。使用简单样例设计一个最简单的、能体现问题核心的样例比如N2, V3手动推导一遍整个过程再与程序输出对比。关注dp数组的含义时刻问自己dp[i][j]当前存储的值是否真的是我定义的那个状态下的最优解复杂度估算错误DP的复杂度通常是状态数乘以转移代价。如果状态数是O(n²)转移是O(n)总复杂度就是O(n³)对于n1000就可能超时。这时需要考虑优化如斜率优化、四边形不等式、滚动数组降维等。5.3 空间优化技巧滚动数组当状态转移只依赖于上一行或前几行的状态时可以使用滚动数组将二维DP压缩成一维大幅节省空间。这在背包问题中尤为常见。以01背包为例原始的二维状态是dp[i][j]表示前i件物品容量j的最大价值。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])。 观察发现dp[i]只依赖于dp[i-1]。因此我们可以只用一维数组dp[j]但在更新时必须逆序枚举j。// 二维版本 for (int i 1; i N; i) { for (int j 0; j V; j) { 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]); } } // 滚动数组优化为一维版本 vectorint dp(V1, 0); for (int i 1; i N; i) { for (int j V; j v[i]; --j) { // 关键逆序 dp[j] max(dp[j], dp[j - v[i]] w[i]); // 这里的dp[j-v[i]]是i-1时刻的值 } }逆序是为了保证在更新dp[j]时dp[j - v[i]]还是上一轮i-1的值。如果正序dp[j - v[i]]可能已经被本轮更新过相当于物品被重复选取这就变成了完全背包的逻辑。这份模板库是我在无数次练习和比赛后沉淀下来的精华它不能替代你对DP原理的深入理解但能在你思路清晰时为你节省大量编码和调试的时间。最后记住DP的精髓在于“状态”和“转移”多刷题、多总结、多思考为什么这样定义状态才是提升的根本。在国赛的战场上希望这份“兵器谱”能助你披荆斩棘。 
长河君 · 2026/8/28 9:08:22 · 阅读 1.2k 蓝桥杯国赛动态规划核心模板：从背包到数位DP的实战指南
1. 项目概述一份来自国赛战场的动态规划“兵器谱”如果你正在备战蓝桥杯国赛或者任何需要用到动态规划DP的算法竞赛那么你大概率和我一样经历过面对复杂状态转移方程时的迷茫以及调试边界条件时的抓狂。DP这个被誉为算法竞赛“分水岭”的题型其核心魅力在于将复杂问题分解为重叠子问题并通过记忆化或递推来高效求解。然而它的难点也恰恰在此——状态定义千变万化转移方程构思精巧稍有不慎便会陷入“想不出来”或“写不出来”的困境。这份“第十二届_国赛蓝桥杯个人模板_DP篇”正是我在多次实战尤其是经历国赛级别的锤炼后整理归纳出的一套核心DP模板与解题框架。它不是一个简单的代码合集而是一套经过验证的“思维兵器谱”和“代码脚手架”。其核心价值在于将常见的DP模型抽象化、模板化让你在面对新题时能快速识别问题本质套用或适配已有框架从而把宝贵的比赛时间用在思考关键的状态设计上而非重复编写基础代码逻辑。无论是刚接触DP的新手还是希望提升解题稳定性的老手这套模板都能提供清晰的路径和可靠的参考。2. DP核心思想与模板设计哲学2.1 动态规划的本质状态、决策与最优子结构动态规划之所以强大是因为它基于一个看似简单却威力巨大的思想利用过去的结果来推导现在。要理解模板首先要吃透这三个核心概念状态State这是描述问题在某个“时刻”或“阶段”情况的变量集合。例如在背包问题中“当前考虑到第i件物品且背包容量剩余j”就是一个状态通常用dp[i][j]表示。设计状态是DP最关键的步骤好的状态应该能唯一确定一个子问题且包含推导后续状态所需的全部信息。决策Decision/Choice在每个状态我们可以做出的选择。例如对于第i件物品决策就是“放入背包”或“不放入背包”。决策会导致状态发生转移。状态转移方程State Transition Equation这是DP的灵魂它定量地描述了如何从已知状态通常是更小的、已解决的状态通过决策推导出当前状态的值。其形式通常为dp[新状态] 最优/聚合(dp[旧状态1], dp[旧状态2], ...)。模板的设计就是针对某一类具有相同状态定义方式和转移逻辑的问题预先将它们的框架搭建好。我们模板库的哲学是覆盖经典模型抽象公共模式提供清晰注释。这样在比赛中你可以像查手册一样快速找到对应模型的骨架然后专注于将具体问题“映射”到这个骨架上。2.2 模板的通用结构与编码规范为了确保模板的清晰性和可用性所有模板都遵循统一的编码结构和注释规范// 模板示例结构 #include bits/stdc.h using namespace std; /** * 模板名称经典01背包问题 * 问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移方程dp[j] max(dp[j], dp[j - v[i]] w[i]) (注意j的遍历顺序) * 复杂度O(N * V) * 注意事项内层循环必须逆序遍历容量以确保每件物品最多被选取一次。 */ void zeroOneKnapSackTemplate() { int N, V; // 物品数量背包容量 cin N V; vectorint v(N 1), w(N 1); // 体积价值。下标从1开始 for (int i 1; i N; i) cin v[i] w[i]; vectorint dp(V 1, 0); // dp数组初始化通常求最大值初始化为0 // 核心递推过程 for (int i 1; i N; i) { // 枚举物品 for (int j V; j v[i]; --j) { // 逆序枚举容量这是01背包的关键 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[V] endl; }注意注释中明确指出了“逆序遍历”这一关键细节和原因。这是模板的精华所在避免使用者因记忆模糊而犯错。3. 经典DP模型模板详解与实战映射3.1 线性DP最长上升子序列LIS及其变种线性DP是基础其状态通常与序列的“位置”线性相关。最长上升子序列LIS是典例。3.1.1 标准O(n²)模板适用于数据规模较小n ≤ 5000的情况思路直观是理解LIS本质的起点。/** * 模板最长上升子序列 (O(n^2)) * 状态定义dp[i] 表示以第i个元素结尾的最长上升子序列长度。 * 转移方程dp[i] max(dp[j]) 1, 对于所有 j i 且 a[j] a[i] * 初始化dp[i] 1 (每个元素自身构成长度为1的子序列) * 结果max(dp[1...n]) */ int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }3.1.2 贪心二分O(n log n)优化模板这是必须掌握的优化版本能处理n高达10^5的情况。其核心是维护一个“潜力序列”d[]d[i]表示长度为i的上升子序列末尾元素的最小可能值。/** * 模板最长上升子序列 (O(n log n)) * 核心维护数组dd[len] x 表示长度为len的LIS的末尾元素最小值为x。 * 流程遍历原数组用二分查找在d中找到第一个大于等于当前元素a[i]的位置pos。 * 如果pos是新的长度即d[pos]未定义或更大则更新d[pos] a[i]。 * 否则用a[i]更新d[pos]因为它为未来更长的子序列提供了更小的末尾值。 * 结果d中被有效更新的最大下标即为LIS长度。 */ int lengthOfLIS_Optimized(vectorint nums) { int n nums.size(); vectorint d; // 潜力数组 d.push_back(nums[0]); for (int i 1; i n; i) { if (nums[i] d.back()) { d.push_back(nums[i]); // 可以延长LIS } else { // 二分查找找到第一个大于等于nums[i]的位置将其替换 auto it lower_bound(d.begin(), d.end(), nums[i]); *it nums[i]; } } return d.size(); // d的长度就是LIS的长度 }实操心得很多变种问题如“最长不下降子序列”、“使序列严格递增的最小修改次数”等都可以基于此模板调整二分比较条件将改为或将lower_bound改为upper_bound。关键在于理解d数组的含义——它维护的是每种长度下最小的末尾值这个“最小”是贪心优化的核心。3.2 背包DP从01背包到分组背包背包问题是DP的“必修课”国赛中常以各种变体出现。3.2.1 01背包ZeroOne Pack上面已给出模板核心是逆序枚举容量确保物品最多选一次。3.2.2 完全背包Complete Pack与01背包的唯一区别是每件物品有无限个。代码上的区别仅仅是正序枚举容量。/** * 模板完全背包问题 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移方程dp[j] max(dp[j], dp[j - v[i]] w[i]) * 关键区别内层对容量的循环是正序j从v[i]到V。因为正序允许在考虑第i件物品时dp[j - v[i]]可能已经包含了第i件物品从而实现无限选取。 */ void completeKnapSackTemplate() { int N, V; cin N V; vectorint v(N1), w(N1); for(int i1; iN; i) cin v[i] w[i]; vectorint dp(V1, 0); for(int i1; iN; i){ for(int jv[i]; jV; j){ // 正序正序正序 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } cout dp[V] endl; }3.2.3 多重背包Multiple Pack每件物品有固定的数量限制s[i]。朴素解法是将其拆分为s[i]个01背包物品但复杂度高。二进制优化是必须掌握的技巧能将复杂度从O(V * Σs[i])降至O(V * Σlog s[i])。/** * 模板多重背包二进制优化 * 思想将数量为s的物品拆分成1, 2, 4, ..., 2^k, c (c s - (2^{k1}-1)) 这些“新物品”。 * 这些新物品的组合可以表示出0~s之间的任意数量且新物品的数量是log s级别的。 * 然后对这些新物品做01背包即可。 */ void multipleKnapSackBinaryOpt() { int N, V; cin N V; vectorint dp(V 1, 0); vectorpairint, int goods; // 存放体积价值 for (int i 0; i N; i) { int v, w, s; cin v w s; // 二进制拆分 for (int k 1; k s; k * 2) { goods.push_back({v * k, w * k}); s - k; } if (s 0) goods.push_back({v * s, w * s}); } // 对拆分后的goods进行01背包 for (auto [vol, val] : goods) { for (int j V; j vol; --j) { dp[j] max(dp[j], dp[j - vol] val); } } cout dp[V] endl; }3.2.4 分组背包Group Pack物品被分为若干组每组内物品互斥最多选一件。这是许多实际问题的模型如课程选修。/** * 模板分组背包 * 状态定义dp[j] 表示容量为j的背包所能获得的最大价值。 * 转移逻辑最外层循环枚举物品组中层循环逆序枚举容量保证每组内最多选一个最内层循环枚举组内物品。 * 核心对于每个容量j我们是在所有组内物品中选一个最优的或不选。 */ void groupKnapSackTemplate() { int N, V; // N组物品背包容量V cin N V; vectorint dp(V 1, 0); for (int i 0; i N; i) { // 枚举组 int s; // 本组物品数量 cin s; vectorint v(s), w(s); for (int k 0; k s; k) cin v[k] w[k]; // 注意容量循环必须在最内层物品循环的外面且逆序 for (int j V; j 0; --j) { // 枚举容量 for (int k 0; k s; k) { // 枚举组内物品 if (j v[k]) { dp[j] max(dp[j], dp[j - v[k]] w[k]); } } } } cout dp[V] endl; }注意事项分组背包的循环顺序是易错点。必须先容量后物品且容量要逆序。可以这样理解对于当前组我们把dp[j]看作一个“临时状态”在枚举组内所有物品的过程中用它们来更新dp[j]而逆序保证了更新dp[j]时用到的dp[j - v[k]]是上一组或更早的状态不会发生本组物品被重复选取。3.3 区间DP枚举分割点的艺术区间DP用于解决涉及区间合并、分割的问题如石子合并、括号匹配等。其状态通常定义为dp[i][j]表示区间[i, j]上的最优解。3.3.1 经典模板石子合并最小代价/** * 模板区间DP - 石子合并最小代价 * 状态定义dp[i][j] 表示合并第i堆到第j堆石子的最小代价。 * 转移方程dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j]), 其中 i k j。 * sum[i][j]是区间[i,j]的石子总重量可以用前缀和快速计算。 * 初始化dp[i][i] 0 (单堆石子无需合并) * 遍历顺序由于计算dp[i][j]需要用到更短的区间结果所以需要按区间长度len从小到大遍历。 */ int stoneMergeMinCost(vectorint stones) { int n stones.size(); vectorint prefix(n 1, 0); for (int i 1; i n; i) prefix[i] prefix[i - 1] stones[i - 1]; vectorvectorint dp(n, vectorint(n, 0)); // 按区间长度遍历 for (int len 2; len n; len) { // len1时代价为0已初始化 for (int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] INT_MAX; // 初始化为无穷大 int sum_ij prefix[j 1] - prefix[i]; for (int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] sum_ij); } } } return dp[0][n - 1]; }3.3.2 区间DP的遍历顺序与优化理解遍历顺序至关重要。必须保证在计算dp[i][j]时其依赖的所有更小区间dp[i][k]和dp[k1][j]都已被计算出来。按长度递增遍历是通用且安全的方法。 对于某些问题如平行四边形优化可以进一步优化内层k的枚举范围但国赛中掌握基础模板已足够应对大部分题目。3.4 状态压缩DP状压DP用比特位表示集合状压DP常用于处理小规模n ≤ 20的集合选择问题如旅行商问题TSP、棋盘覆盖、任务安排等。其核心是用一个整数的二进制位来表示一个集合第i位为1表示元素i在集合中。3.4.1 经典模板旅行商问题TSP/** * 模板状态压缩DP - 旅行商问题TSP * 问题从城市0出发访问所有城市恰好一次后回到0求最短路径。 * 状态定义dp[S][i] 表示已经访问过的城市集合为S二进制表示且当前位于城市i的最小花费。 * 转移方程dp[S][i] min(dp[S\{i}][j] dist[j][i]), 其中 j 属于集合 S\{i}。 * 初始化dp[10][0] 0表示从城市0出发只访问了城市0花费为0。 * 结果min(dp[(1n)-1][i] dist[i][0])即访问完所有城市后从最后所在城市i返回0的总花费。 */ int tsp(vectorvectorint dist) { int n dist.size(); int state_num 1 n; vectorvectorint dp(state_num, vectorint(n, INT_MAX / 2)); // 防止加法溢出 dp[1][0] 0; // 起点在0状态为只包含0 for (int S 1; S state_num; S) { // 枚举所有状态 for (int i 0; i n; i) { if (!(S i 1)) continue; // 状态S中必须包含i if (dp[S][i] INT_MAX / 2) continue; // 无效状态 // 尝试从状态S中从i转移到下一个未访问的城市j for (int j 0; j n; j) { if (S j 1) continue; // j不能在S中未访问 int next_S S | (1 j); dp[next_S][j] min(dp[next_S][j], dp[S][i] dist[i][j]); } } } int ans INT_MAX; int full_state (1 n) - 1; for (int i 1; i n; i) { // 从任意非0城市i返回0 if (dp[full_state][i] INT_MAX / 2) { ans min(ans, dp[full_state][i] dist[i][0]); } } return ans; }实操心得状压DP的难点在于对二进制操作要非常熟练。常用操作有S (1 i)判断元素i是否在集合S中。S | (1 i)将元素i加入集合S。S ~(1 i)将元素i从集合S中移除。for(int sub S; sub; sub (sub-1) S)枚举集合S的所有非空子集。这个技巧在需要枚举子集进行转移时非常有用。3.5 数位DP统计数字区间内的特定数数位DP用于解决与数字的数位相关的问题例如统计区间[L, R]内有多少个数满足某些性质如不含数字4、是回文数、各位数字之和等。其核心是记忆化搜索DFS按位处理并利用“是否达到上限is_limit”和“前导零is_num”等状态来剪枝。3.5.1 通用模板框架/** * 模板数位DP通用框架记忆化搜索 * 问题求区间[0, num]内满足条件P的数字个数。 * 状态定义dp[pos][state][is_limit][is_num] * - pos: 当前正在处理第几位从高位到低位。 * - state: 一个与题目条件相关的状态如前面数字的和、前面数字的模数、是否包含某数字等。 * - is_limit: 当前位是否受到num对应位的限制。若为true则当前位最大只能取s[pos]否则可取0-9。 * - is_num: 当前位之前是否已经填过数字即是否跳过了前导零。用于处理前导零不影响状态的情况。 * 返回值从pos位开始在给定状态下能构造出的满足条件的数字个数。 */ class DigitDP { string s; // 将上界num转为字符串方便按位处理 vectorvectorvectorvectorint dp; // 记忆化数组维度根据state定义 // 根据具体问题定义state的维度和初始值 public: int solve(int num) { s to_string(num); int n s.length(); // 初始化dp为-1表示未计算。维度[pos][state_dim1][state_dim2][2][2] dp.assign(n, vector...(..., -1)); // 此处根据具体state定义 // 从最高位开始搜索起始状态位置0初始state受上限限制尚未开始填数is_numfalse return dfs(0, init_state, true, false); } int dfs(int pos, int state, bool is_limit, bool is_num) { if (pos s.size()) { // 递归终点所有位处理完毕 return is_num ? 1 : 0; // 如果是一个有效的数字至少填了一位返回1否则返回0处理全0情况 } // 记忆化如果不受限制且已经是一个有效数字且状态已计算过直接返回 if (!is_limit is_num dp[pos][state] ! -1) { return dp[pos][state]; } int res 0; int up is_limit ? s[pos] - 0 : 9; // 当前位能取的最大值 // 如果之前一直没填数可以选择继续跳过填0但这不是一个有效数字位 if (!is_num) { res dfs(pos 1, state, false, false); // 跳过is_limit变为false因为前导0不受原数限制 } // 枚举当前位可以填的数字 int start is_num ? 0 : 1; // 如果之前没填过数不能填0否则还是前导零 for (int d start; d up; d) { if (!isValid(d, state)) continue; // 根据题目条件判断当前数字d是否合法 int next_state getNextState(state, d); // 根据当前状态和数字d计算下一个状态 res dfs(pos 1, next_state, is_limit (d up), true); } // 记录状态只有当不受限制且是有效数字时才记录因为受限制的状态是唯一的不需要记忆化 if (!is_limit is_num) { dp[pos][state] res; } return res; } // 以下两个函数需要根据具体问题实现 bool isValid(int digit, int state) { // 判断在当前state下digit是否允许被填入 // 例如不能填4或不能连续填两个1等 return true; // 示例 } int getNextState(int old_state, int digit) { // 根据旧状态和填入的数字计算新状态 // 例如新状态为各位数字之和则返回 old_state digit return old_state; // 示例 } };注意事项数位DP的模板看似复杂但结构固定。关键在于根据题目定义state以及实现isValid和getNextState函数。is_limit和is_num是两个核心的剪枝和状态区分标志务必理解其作用。处理区间[L, R]的问题时通常转化为solve(R) - solve(L-1)。4. 国赛真题中的DP实战分析与模板应用理论需要结合实战。我们选取几道经典的蓝桥杯国赛DP真题看看如何将问题抽象并套用或修改上述模板。4.1 真题解析一矩阵中的最大权值路径线性DP变种问题简述给定一个N x M的矩阵每个格子有分值。从左上角走到右下角每次只能向右或向下求路径最大分值之和。模板映射这是最基础的二维线性DP状态dp[i][j]表示走到(i, j)格子的最大分值。转移方程dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]初始化dp[0][0] grid[0][0]第一行和第一列需要单独初始化因为只能从一个方向来。代码实现几乎可以直接套用线性DP的思路注意边界处理。int maxPathSum(vectorvectorint grid) { int n grid.size(), m grid[0].size(); vectorvectorint dp(n, vectorint(m, 0)); dp[0][0] grid[0][0]; for (int i 1; i n; i) dp[i][0] dp[i-1][0] grid[i][0]; for (int j 1; j m; j) dp[0][j] dp[0][j-1] grid[0][j]; for (int i 1; i n; i) { for (int j 1; j m; j) { dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } return dp[n-1][m-1]; }4.2 真题解析二带限制的整数划分背包DP变种问题简述将整数N划分成若干个正整数之和且每个正整数不超过M求划分方案数。例如N5, M3划分有11111, 1112, 113, 122, 23。模板映射这可以看作是一个完全背包问题。背包容量是N物品是1, 2, ..., M每个物品可以无限取因为一个数字可以重复出现求恰好装满背包的方案数。状态定义dp[j]表示凑成总和为j的方案数。转移方程dp[j] dp[j - i]其中i是物品数字大小从1到M。初始化dp[0] 1凑成0的方案数为1即什么都不选。代码实现注意这是求方案数所以是累加。int partitionNumber(int N, int M) { vectorint dp(N 1, 0); dp[0] 1; for (int i 1; i M; i) { // 枚举“物品”数字i for (int j i; j N; j) { // 完全背包正序枚举容量 dp[j] dp[j - i]; } } return dp[N]; }4.3 真题解析三复杂状态转移的区间DP问题简述给定一个字符串添加最少的字符使其成为回文串。求最少添加字符数。模板映射这是一个区间DP问题。状态dp[i][j]表示将子串s[i...j]变成回文串所需的最少添加次数。转移分析如果s[i] s[j]那么两端字符已经配对问题转化为dp[i1][j-1]。如果s[i] ! s[j]那么可以在左边添加一个s[j]或者在右边添加一个s[i]。即dp[i][j] min(dp[i1][j], dp[i][j-1]) 1。初始化单个字符本身就是回文dp[i][i] 0。相邻字符如果相等则为0否则为1。代码实现按区间长度递增遍历。int minAddToPalindrome(string s) { int n s.length(); vectorvectorint dp(n, vectorint(n, 0)); for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { dp[i][j] (len 2) ? 0 : dp[i 1][j - 1]; } else { dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1; } } } return dp[0][n - 1]; }5. 模板使用心法与调试技巧5.1 如何选择与修改模板识别问题类型首先判断问题属于哪一大类线性、背包、区间、状压、树形、数位等。看数据范围是重要线索n≤20可能是状压n≤100可能是区间或普通DP涉及“选或不选”和“容量”可能是背包。定义状态这是最关键的一步。问自己需要哪些信息才能唯一确定一个子问题并且能推导出后续状态状态维度可能是一维位置、二维位置状态、甚至更多。推导转移方程思考从哪些已知状态能转移到当前状态。写出方程后务必检查边界条件和初始化。确定遍历顺序确保在计算dp[x]时它所依赖的状态都已经被计算过。对于线性DP通常顺序遍历对于区间DP按长度遍历对于背包注意01背包逆序、完全背包正序。适配模板将你定义的状态和方程套入最相近的模板框架中。例如如果你的问题是一个变种的背包就基于01背包或完全背包的模板进行修改。5.2 调试DP程序的常见“坑点”数组越界这是最常见的运行时错误。特别是在处理dp[i-1],dp[i-v]时一定要确保下标大于等于0。在竞赛中可以将dp数组大小稍微开大一点例如5或10并从下标1开始使用可以避免很多边界麻烦。初始化错误求最大值/最小值通常初始化为负无穷/正无穷但dp[0]或起点状态需要根据题意设为0或其他特定值。求方案数通常dp[0] 1其他初始为0。务必仔细考虑所有边界状态的初始值。遍历顺序错误尤其是背包问题。牢记01背包逆序完全背包正序分组背包先容量后物品且逆序。可以这样记忆“逆序保证唯一性正序允许无限性”。状态转移方程逻辑错误这是最隐蔽的错误。建议打印DP表对于小规模样例将整个dp数组打印出来与手动计算的结果对比。使用简单样例设计一个最简单的、能体现问题核心的样例比如N2, V3手动推导一遍整个过程再与程序输出对比。关注dp数组的含义时刻问自己dp[i][j]当前存储的值是否真的是我定义的那个状态下的最优解复杂度估算错误DP的复杂度通常是状态数乘以转移代价。如果状态数是O(n²)转移是O(n)总复杂度就是O(n³)对于n1000就可能超时。这时需要考虑优化如斜率优化、四边形不等式、滚动数组降维等。5.3 空间优化技巧滚动数组当状态转移只依赖于上一行或前几行的状态时可以使用滚动数组将二维DP压缩成一维大幅节省空间。这在背包问题中尤为常见。以01背包为例原始的二维状态是dp[i][j]表示前i件物品容量j的最大价值。转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])。 观察发现dp[i]只依赖于dp[i-1]。因此我们可以只用一维数组dp[j]但在更新时必须逆序枚举j。// 二维版本 for (int i 1; i N; i) { for (int j 0; j V; j) { 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]); } } // 滚动数组优化为一维版本 vectorint dp(V1, 0); for (int i 1; i N; i) { for (int j V; j v[i]; --j) { // 关键逆序 dp[j] max(dp[j], dp[j - v[i]] w[i]); // 这里的dp[j-v[i]]是i-1时刻的值 } }逆序是为了保证在更新dp[j]时dp[j - v[i]]还是上一轮i-1的值。如果正序dp[j - v[i]]可能已经被本轮更新过相当于物品被重复选取这就变成了完全背包的逻辑。这份模板库是我在无数次练习和比赛后沉淀下来的精华它不能替代你对DP原理的深入理解但能在你思路清晰时为你节省大量编码和调试的时间。最后记住DP的精髓在于“状态”和“转移”多刷题、多总结、多思考为什么这样定义状态才是提升的根本。在国赛的战场上希望这份“兵器谱”能助你披荆斩棘。