「动态规划」在信息学竞赛真题中出现 109 次，覆盖 NOIP 普及组 初赛、NOIP 提高组 初赛、CSP 提高级、CSP 入门级、GESP 五级、GESP 七级、GESP 六级、GESP 八级、GESP 四级。下面按考试级别列出每一道题的题号、答案与一句话解题思路，可以按考点横向刷，也可以顺着套卷纵向练。
怎么用这一页：先看下面的「命中题目速查」，挑 2~3 道做；做完对照每题的「常见错误」检查自己是不是踩了同一个坑；同一个考点连续错两次，就去知识点精讲把规则补齐再回来刷。
-
第 8 题
答案：A
· 选择题 · GESP 七级样题（C++ 组）
拿到题先别急着背定义，脑子里过一遍DP和分治、贪心的区别：分治是把大问题拆成互不干扰的小块，DP拆出来的小块是互相‘打架’的，这就是重叠子问题。
看完整解析 →
-
第 10 题
答案：C
· 选择题 · GESP 七级样题（C++ 组）
这道题考的是二维 DP 循环顺序与依赖方向。拿到题先画依赖图：dp[i][j] 需要 dp[i 1][j] 和 dp[i][j 1]，所以必须保证计算当前格子时，这两个值已经算好。
看完整解析 →
-
第 21 题
答案：A
· 判断题 · GESP 七级样题（C++ 组）
这道题考动态规划的核心定义。拿到判断题别急着翻书背定义，直接想：动态规划的本质是什么？是‘分而治之’把大问题拆成小问题，然后怎么把这些小问题的解拼起来？答案就是状态转移方程，它是DP的骨架，没有它DP就散了。
看完整解析 →
-
第 2 题
答案：D
· 选择题 · GESP 202312 C++ 七级
这题是经典的区间 DP 模型，核心在于识别出合并代价与区间和的关系，以及分裂点 k 的正确范围。拿到题先别急着套公式，盯着代码里 f[i][j] 的更新过程，你会发现那个 s[j] s[i 1] 其实是个常数，完全可以提…
看完整解析 →
-
第 3 题
答案：B
· 选择题 · GESP 202312 C++ 七级
这题考的是动态规划里最长上升子序列（LIS）的经典写法，命题人把输出拆成了两行：先一行把每个 f[i] 都打出来，再单独一行输出最终答案 ans。拿到题先别急着算 LIS 长度，要盯着代码最后那个循环——它把 f 数组每…
看完整解析 →
-
第 8 题
答案：C
· 选择题 · GESP 202312 C++ 七级
这题考动态规划的空间复杂度分析。拿到代码先看状态转移方程，判断当前状态依赖哪些上一轮的数据，就能直接看出能不能压缩维度，别被二维数组的表象迷惑了。
看完整解析 →
-
第 11 题
答案：D
· 选择题 · GESP 202312 C++ 七级
这题本质是图遍历，拿到题先别想DP，直接建反向图（或正向图找能到的点），从目标课程出发跑BFS或DFS就能把全部先修课搜出来，动态规划在这里纯属画蛇添足。
看完整解析 →
-
第 19 题
答案：A
· 判断题 · GESP 202312 C++ 七级
这题考动态规划适用范围。拿到题先别急着写代码，想清楚：最大子段和能用贪心吗？能分治吗？能不能用动态规划？DP的核心是‘最优子结构’——当前最优解包含子问题的最优解，最大子段和显然满足这一点，所以选A。
看完整解析 →
-
第 23 题
答案：B
· 判断题 · GESP 202312 C++ 七级
这题考动态规划的本质理解，核心是：状态转移方程只是定义了‘怎么算’，但没解决‘算多少次’的问题。拿到题先想：递归不加记忆化会怎样？指数级爆炸就是答案。
看完整解析 →
-
第 19 题
答案：B
· 判断题 · GESP 202403 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 23 题
答案：A
· 判断题 · GESP 202403 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 3 题
答案：A
· 选择题 · GESP 202406 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP 202406 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 12 题
答案：C
· 选择题 · GESP 202409 C++ 七级
模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。
看完整解析 →
-
第 10 题
答案：D
· 选择题 · GESP 202412 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 12 题
答案：A
· 选择题 · GESP 202412 C++ 七级
模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。
看完整解析 →
-
第 10 题
答案：D
· 选择题 · GESP 202503 C++ 七级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 11 题
答案：A
· 选择题 · GESP 202503 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 13 题
答案：B
· 选择题 · GESP 202503 C++ 七级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 14 题
答案：B
· 选择题 · GESP 202503 C++ 七级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP 202503 C++ 七级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 10 题
答案：B
· 选择题 · GESP 202506 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 24 题
答案：B
· 判断题 · GESP 202506 C++ 七级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 10 题
答案：D
· 选择题 · GESP 202509 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 2 题
答案：A
· 选择题 · GESP 202512 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 4 题
答案：C
· 选择题 · GESP 202512 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 20 题
答案：A
· 判断题 · GESP 202512 C++ 七级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 19 题
答案：B
· 判断题 · GESP 202603 C++ 七级
贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。
看完整解析 →
-
第 5 题
答案：C
· 选择题 · GESP 202606 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 6 题
答案：C
· 选择题 · GESP 202606 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 7 题
答案：D
· 选择题 · GESP 202606 C++ 七级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 15 题
答案：D
· 选择题 · GESP 202606 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 18 题
答案：B
· 判断题 · GESP 202606 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202606 C++ 七级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 4 题
答案：B
· 选择题 · GESP202609 C++ 七级
看到"网格路径"先想组合数公式。n×m 格点（即 (n−1)×(m−1) 个格子）从左上到右下只允许向右、向下，总步数固定为 (n−1)+(m−1)，只需从中选若干步向右（或向下）即可，路径数 = C(n+m−2, n−…
看完整解析 →
-
第 6 题
答案：B
· 选择题 · GESP202609 C++ 七级
看到题先想：合并代价是两堆之和，本质是构造一棵二叉树，叶子是初始石子数，内部节点权值是子树和。最小总代价=所有内部节点权值之和。这类题通法是区间DP：枚举区间长度，再枚举分割点，dp[i][j]表示合并第i到j堆的最小代…
看完整解析 →
-
第 11 题
答案：A
· 选择题 · GESP202609 C++ 七级
LCS 经典 DP 题，核心是区分两种情形：当 s₁[i−1] = s₂[j−1] 时，两字符能同时纳入公共子序列，状态转移为 dp[i][j] = dp[i−1][j−1] + 1；当不相等时，只能舍弃一个字符，取 d…
看完整解析 →
-
第 22 题
答案：A
· 判断题 · GESP202609 C++ 七级
看到0/1背包先想二维dp[i][j]，优化成一维dp[j]后，更新dp[j]依赖dp[j w]，必须保证dp[j w]是上一轮的值。因此容量循环必须从大到小枚举，否则同一物品会被重复使用。
看完整解析 →
-
第 13 题
答案：C
· 选择题 · GESP 202309 C++ 六级
这题代码看着像递归，但问的是‘算法’。别被递归写法带偏，先剥离代码看数学本质：它把大问题拆成两个小问题（N 1 和 N 2）然后合并，这就是动态规划里最经典的斐波那契递推模型。
看完整解析 →
-
第 8 题
答案：D
· 选择题 · GESP 202312 C++ 六级
这题表面考函数写法，实则考复杂度意识。拿到题先看调用树：fiboA 每次都要把问题拆成两个子问题，中间层会重复算无数次；fiboB 用数组把算过的值存起来，下次直接取。记住：代码行数短不代表快，指数级时间复杂度才是致命伤…
看完整解析 →
-
第 7 题
答案：C
· 选择题 · GESP 202403 C++ 六级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 11 题
答案：A
· 选择题 · GESP 202403 C++ 六级
贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。
看完整解析 →
-
第 17 题
答案：A
· 判断题 · GESP 202403 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 11 题
答案：A
· 选择题 · GESP 202406 C++ 六级
贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。
看完整解析 →
-
第 12 题
答案：D
· 选择题 · GESP 202406 C++ 六级
斐波那契数列：f(1)=f(2)=1，f(n)=f(n 1)+f(n 2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。
看完整解析 →
-
第 14 题
答案：B
· 选择题 · GESP 202409 C++ 六级
贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。
看完整解析 →
-
第 15 题
答案：C
· 选择题 · GESP 202409 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP 202409 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202409 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 14 题
答案：B
· 选择题 · GESP 202412 C++ 六级
贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。
看完整解析 →
-
第 15 题
答案：C
· 选择题 · GESP 202412 C++ 六级
背包问题：01背包倒序枚举容量，完全背包正序枚举容量。状态 dp[i][j] 表示前i个物品容量j的最大价值。
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP 202412 C++ 六级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 7 题
答案：B
· 选择题 · GESP 202503 C++ 六级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 22 题
答案：A
· 判断题 · GESP 202503 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 15 题
答案：C
· 选择题 · GESP 202506 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202506 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 15 题
答案：D
· 选择题 · GESP 202509 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 24 题
答案：B
· 判断题 · GESP 202509 C++ 六级
斐波那契数列：f(1)=f(2)=1，f(n)=f(n 1)+f(n 2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202509 C++ 六级
仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。
看完整解析 →
-
第 15 题
答案：B
· 选择题 · GESP 202512 C++ 六级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 14 题
答案：C
· 选择题 · GESP 202603 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 15 题
答案：A
· 选择题 · GESP 202603 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 24 题
答案：B
· 判断题 · GESP 202603 C++ 六级
背包问题：01背包倒序枚举容量，完全背包正序枚举容量。状态 dp[i][j] 表示前i个物品容量j的最大价值。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202603 C++ 六级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 14 题
答案：B
· 选择题 · GESP 202606 C++ 六级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 15 题
答案：A
· 选择题 · GESP 202606 C++ 六级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 25 题
答案：A
· 判断题 · GESP 202606 C++ 六级
动态规划三要素：① 状态定义；② 状态转移方程；③ 初始条件/边界。先写递归暴力，再找重叠子问题优化。
看完整解析 →
-
第 13 题
答案：B
· 选择题 · GESP202609 C++ 六级
看到"走1级或2级"立刻想到斐波那契递推。核心观察：第i级只能从i 1或i 2跳过来，所以dp[i] = dp[i 1] + dp[i 2]。边界是dp[1]=1, dp[2]=2，循环从3填到n即可。这类题通法是：先找…
看完整解析 →
-
第 14 题
答案：C
· 选择题 · GESP202609 C++ 六级
看到这题先想"最优子结构"和"重叠子问题"——这是动态规划的标志性特征。题目要求选互不相邻元素，意味着选第 i 个时，第 i 1 个必须放弃，因此状态转移只能来自 dp[i 1]（不选 a[i]）或 dp[i 2]+a[…
看完整解析 →
-
第 15 题
答案：A
· 选择题 · GESP202609 C++ 六级
看到 0/1 背包的一维 DP 写法，第一反应是"为什么内层循环要从大到小"。因为一维数组复用，如果从小到大枚举容量，当前物品会被重复使用（相当于完全背包）。从大到小枚举，确保每次更新 dp[w] 时，dp[w weig…
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP202609 C++ 六级
看到双层循环先盯内层方向：0/1背包内层倒序，完全背包内层正序。本题内层从 weight[i] 到 W 递增，说明同种物品可重复选，符合完全背包特征。再验证状态转移方程 dp[w] = max(dp[w], dp[w w…
看完整解析 →
-
第 15 题
答案：C
· 选择题 · GESP 202312 C++ 八级
这题考的是网格最短路径的DP，但陷阱全在'下标偏移'上。别盯着公式背，先看循环：i和j都是从0跑到的，横线处若直接写dis[i][j]，当i=0或j=0时就会访问负下标，直接越界。所以必须把循环变量整体+1，让计算从di…
看完整解析 →
-
第 18 题
答案：A
· 判断题 · GESP 202312 C++ 八级
这题是个送分概念题，核心就是把杨辉三角和组合数 C(n,k) 对应起来。拿到题先别慌，直接回忆二项式定理展开式里第几行第几个数是什么，再对照题目描述里的‘行’‘列’定义，看是不是完全吻合，通常一眼就能判断。
看完整解析 →
-
第 21 题
答案：A
· 判断题 · GESP 202312 C++ 八级
这题考动态规划时间复杂度构成。拿到题先想：DP 把大问题拆成多少个子问题（状态数），再想解每个子问题要几步（转移代价），两者相乘就是总耗时，这就是乘法原理在算法分析里的直接应用。
看完整解析 →
-
第 13 题
答案：C
· 选择题 · GESP 202403 C++ 八级
模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。
看完整解析 →
-
第 9 题
答案：A
· 选择题 · GESP 202409 C++ 八级
排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。
看完整解析 →
-
第 13 题
答案：B
· 选择题 · GESP 202409 C++ 八级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 8 题
答案：B
· 选择题 · GESP 202412 C++ 八级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 11 题
答案：C
· 选择题 · GESP 202412 C++ 八级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 12 题
答案：A
· 选择题 · GESP 202503 C++ 八级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 10 题
答案：A
· 选择题 · GESP 202506 C++ 八级
位运算：&（与）、 （或）、^（异或）、~（取反）、<<（左移）、 （右移）。异或性质：a^a=0，a^0=a。
看完整解析 →
-
第 13 题
答案：D
· 选择题 · GESP 202506 C++ 八级
STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。
看完整解析 →
-
第 8 题
答案：A
· 选择题 · GESP 202509 C++ 八级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 6 题
答案：C
· 选择题 · GESP 202512 C++ 八级
根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。
看完整解析 →
-
第 12 题
答案：B
· 选择题 · GESP 202512 C++ 八级
模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。
看完整解析 →
-
第 25 题
答案：B
· 判断题 · GESP 202603 C++ 八级
分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。
看完整解析 →
-
第 4 题
答案：A
· 选择题 · GESP 202606 C++ 八级
排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。
看完整解析 →
-
第 3 题
答案：B
· 选择题 · GESP202609 C++ 八级
看到这题先想区间 DP 框架：dp[i][j] 表示合并第 i 到 j 堆的最小代价，状态转移是枚举中间分割点 k，dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i..j))。因为…
看完整解析 →
-
第 12 题
答案：A
· 选择题 · GESP202609 C++ 八级
Floyd 三重循环的核心是"逐步扩大中间顶点集合"。外层 k 控制允许作为中间点的顶点编号上限，内层 i、j 枚举所有点对。每次迭代后，dist[i][j] 存储的是"仅用编号≤k 的顶点作中间点"的最短距离。这是典型…
看完整解析 →
-
第 24 题
答案：A
· 判断题 · GESP202609 C++ 八级
滚动数组的本质是压缩存储维度，用循环变量覆盖旧状态。时间复杂度取决于状态数和转移次数，与存储方式无关。因此滚动数组只能降空间、不降时间，答案选 A。
看完整解析 →
粤公网安备44200102446416号 ·
意见反馈 ·
zsweiluo@163.com