> 适用对象：准备 GESP C++ 七级考试的学生（建议已掌握一维 DP，正在学习二维 DP）
> 模块权重：约 11%（编程题第二大来源，仅次于图论）
> 编程题命中率：每次考试大概率出现一道 DP 题（背包 / 二维 DP / LIS）
> 版本：2026.05 更新，基于 2023.12 ~ 2025.6 共 7 次真题分析
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
目录
1. 动态规划基础概念
2. 一维动态规划
3. 二维动态规划
4. 0-1 背包问题
5. LIS 最长上升子序列
6. LCS 最长公共子序列
7. 区间动态规划
8. DP 优化技巧
9. 练习题推荐
10. 附录
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 动态规划基础概念
1.1 什么是动态规划？
生活类比：你站在楼梯底部，每次可以爬 1 级或 2 级台阶，问爬到第 n 级台阶有多少种不同的方法？
这就是动态规划的核心思想：
> 把大问题拆成小问题，把小问题的答案存起来，避免重复计算。
1.2 动态规划的两个关键性质
性质 说明 例子 最优子结构 大问题的最优解，包含小问题的最优解 最短路径问题：A→C 的最短路，一定包含 A→B 的最短路 重叠子问题 计算过程中，同一个子问题会被反复用到 斐波那契：f(5) 和 f(4) 都要算 f(3)，算两次浪费
1.3 动态规划的解题步骤
四步走：
1.4 动态规划 VS 分治 VS 贪心
方法 子问题是否重叠 是否要求最优子结构 例子 动态规划 ✅ 是 ✅ 是 背包、LIS、LCS 分治 ❌ 否（子问题独立） 不一定 归并排序、快速排序 贪心 ❌ 否 ✅ 是，但更强（局部最优=全局最优） 找零钱（贪心能解决的特殊情况）
> 一句话区分：DP 是「记住答案再复用」，分治是「分开算再合并」，贪心是「每步都选当前看起来最好的」。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维动态规划
2.1 斐波那契数列（DP 入门）
问题：f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)，求 f(n)。
❌ 错误写法（递归，会超时）
问题分析：f(5) 要算 f(4)+f(3)，f(4) 又要算 f(3)+f(2)……f(3) 被算了两次！
✅ 正确写法一：记忆化搜索（自顶向下）
✅ 正确写法二：递推（自底向上，推荐！）
> 为什么递推（写法二）更好？
>
> 1. 没有递归调用，不会栈溢出
> 2. 代码更简单
> 3. 速度更快（没有函数调用开销）
> GESP 考试推荐用递推（自底向上）写法！
2.2 爬楼梯问题
问题：每次可以爬 1 级或 2 级，爬到第 n 级有多少种不同的方法？
状态定义：dp[i] = 爬到第 i 级台阶的方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
* 最后一步走 1 级：前面有 dp[i-1] 种方法
* 最后一步走 2 级：前面有 dp[i-2] 种方法
代码模板：
2.3 最大子数组和
问题：给一个整数数组，找一个连续的子数组，使得它们的和最大。
例如：[-2,1,-3,4,-1,2,1,-5,4] → 最大子数组是 [4,-1,2,1]，和为 6。
状态定义：dp[i] = 以第 i 个数结尾的最大子数组和
状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
* 要么自己单独开头（不要前面的）
* 要么接在前面的最大子数组后面
代码模板：
2.4 一维 DP 练习题推荐
题号 题名 难度 训练要点 P1255 跳楼梯 ⭐ 入门 斐波那契/爬楼梯 P1002 过河卒 ⭐⭐ 普及 一维/二维 DP、边界处理 P1115 最大子段和 ⭐⭐ 普及 最大子数组和 P8707 斐波那契数列 ⭐ 入门 递推/记忆化
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 二维动态规划
3.1 概念讲解
一维 DP 的「状态」只有一个维度（通常是位置 i），二维 DP 的状态有两个维度（通常是位置 i 和位置 j）。
最经典的二维 DP 问题：网格路径问题。
3.2 网格路径问题
问题：有一个 m × n 的网格，机器人从左上角 (0,0) 出发，每次只能向右或向下走，问到达右下角 (m-1, n-1) 有多少种不同的路径？
思路分析
状态定义：dp[i][j] = 从 (0,0) 走到 (i,j) 的路径数
状态转移方程：
边界条件：
* 第一行：只能从左边来 → dp[0][j] = 1
* 第一列：只能从上面来 → dp[i][0] = 1
代码模板
3.3 带障碍的网格路径
问题升级：网格中某些格子有障碍（不能走），求路径数。
关键变化：遇到障碍格时，dp[i][j] = 0（没有路径能到达这里）。
3.4 最小路径和
问题：网格中每个格子有一个数字（代价），从左上角走到右下角，每次只能向右或向下，求经过格子的数字之和的最小值。
状态定义：dp[i][j] = 从 (0,0) 走到 (i,j) 的最小路径和
状态转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
3.5 二维 DP 练习题推荐
题号 题名 难度 训练要点 P1002 过河卒 ⭐⭐ 普及 二维 DP、障碍处理 P1508 Likecloud-吃、吃、吃 ⭐⭐ 普及 二维 DP、反向递推 P1507 NASA的食物计划 ⭐⭐⭐ 普及- 二维费用背包（进阶） P1164 小A点菜 ⭐⭐ 普及 二维 DP 思想、方案计数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 0-1 背包问题
4.1 概念讲解
生活类比：你有一个容量为 W 的背包，面前有 n 件物品，每件物品有重量 w[i] 和价值 v[i]。每件物品只能选一次（0-1 的含义），问背包能装下的物品的最大总价值是多少？
4.2 标准二维 DP 解法
状态定义：dp[i][j] = 考虑前 i 件物品，背包容量为 j 时，能获得的最大价值
状态转移方程：
边界条件：dp[0][j] = 0（不考虑任何物品时，价值为 0）
代码模板（二维，好理解）
4.3 滚动数组优化（★ 高频考点！）
问题：二维数组 dp[1005][1005] 占用约 4MB 内存，如果 n 和 W 都很大（如 10⁵），会内存超限！
优化思路：dp[i][...] 只和 dp[i-1][...] 有关，不需要存所有行，只需要「上一行」和「当前行」。
更进一步的优化：只用一行数组！但遍历顺序必须反过来（从 W 到 w[i]）。
代码模板（一维优化版，考试推荐！）
> 记忆口诀：
>
> * 0-1 背包：容量反向遍历（j = W; j >= w[i]; j--）
> * 完全背包（每件物品可选无限次）：容量正向遍历（j = w[i]; j <= W; j++）
4.4 完全背包问题（对比学习）
区别：0-1 背包每件物品只能选一次，完全背包每件物品可以选无限次。
4.5 背包问题练习题推荐
题号 题名 难度 类型 训练要点 P1048 采药 ⭐ 入门 0-1 背包 背包入门、一维优化 P1616 疯狂的采药 ⭐⭐ 普及 完全背包 完全背包、大容量 P1049 装箱问题 ⭐ 入门 0-1 背包（变种） 背包求能否装满 P1833 樱花 ⭐⭐⭐ 普及- 混合背包 0-1 + 完全 + 多重 P1164 小A点菜 ⭐⭐ 普及 0-1 背包（方案数） 方案计数型 DP
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. LIS 最长上升子序列
5.1 概念讲解
问题：给一个数组，找出一个子序列（不一定连续），使得这个子序列是严格上升的，且长度最长。
5.2 O(N²) DP 解法（好理解，适合入门）
状态定义：dp[i] = 以第 i 个数结尾的最长上升子序列的长度
状态转移方程：
边界条件：每个数自己构成一个长度为 1 的子序列 → dp[i] = 1
代码模板（O(N²)）
时间复杂度：O(n²)，n ≤ 1000 时可以用。
5.3 O(N LOG N) 优化解法（★ GESP 高频！）
思路：维护一个数组 tail，tail[k] 表示「长度为 k 的上升子序列的最小结尾值」。
关键操作：在 tail 数组中用二分查找找到第一个 ≥ a[i] 的位置，用 a[i] 替换它。
代码模板（O(N LOG N)，推荐掌握！）
> lower_bound 详解：
>
> * lower_bound(first, last, val) 返回指向「第一个 ≥ val 的元素」的迭代器
> * 如果要找「第一个 > val 的元素」，用 upper_bound
> * 需要 #include <algorithm>
5.4 LIS 练习题推荐
题号 题名 难度 训练要点 P1020 导弹拦截 ⭐⭐ 普及 LIS + 最长不上升子序列 P1439 公共子序列（LCS 转 LIS） ⭐⭐⭐ 普及- LCS 的优化解法 P1091 合唱队形 ⭐⭐ 普及 LIS + 最长下降子序列
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. LCS 最长公共子序列
6.1 概念讲解
问题：给两个字符串（或数组），找一个子序列（不一定连续），它同时是这两个字符串的子序列，且长度最长。
> 子序列 vs 子串：
>
> * 子序列：不一定连续（可以跳过某些字符）
> * 子串：必须连续
> LCS 找的是子序列！
6.2 状态定义与转移方程
状态定义：dp[i][j] = 字符串1的前 i 个字符 和 字符串2的前 j 个字符 的 LCS 长度
状态转移方程：
边界条件：dp[0][j] = 0，dp[i][0] = 0（空串和任何串的 LCS 长度为 0）
6.3 代码模板
时间复杂度：O(nm)，n 和 m 都在 1000 以内可以用。
6.4 LCS 练习题推荐
题号 题名 难度 训练要点 P1439 公共子序列 ⭐⭐⭐ 普及- LCS 标准模板 P1000 豆腐块 ⭐⭐ 普及 LCS 思想应用
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 区间动态规划
7.1 概念讲解
区间 DP 的状态定义是「区间」[l, r]，即：考虑从位置 l 到位置 r 这个区间的最优解。
典型问题：石子合并。
7.2 石子合并问题
问题：有 n 堆石子排成一排，每次可以合并相邻的两堆，合并的代价是两堆石子的总数。问把所有石子合并成一堆的最小总代价是多少？
状态定义：dp[l][r] = 合并第 l 堆到第 r 堆石子所需的最小代价
状态转移方程：
关键：需要先计算小区间，再计算大区间 → 区间长度从小到大枚举！
代码模板
时间复杂度：O(n³)，n ≤ 100 时可以用。
7.3 区间 DP 要点
要点 说明 枚举顺序 区间长度从小到大，保证小区间先算完 前缀和 快速计算 sum(l,r) = sum[r] - sum[l-1] 初始化 dp[i][i] = 0（一个元素不需要合并） GESP 考查频率 中低频，但理解思路有助于应对新题
7.4 区间 DP 练习题推荐
题号 题名 难度 训练要点 P1775 石子合并（弱化版） ⭐⭐ 普及 区间 DP 入门 P1880 石子合并（环形） ⭐⭐⭐ 普及- 环形区间 DP
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. DP 优化技巧
8.1 滚动数组（已讲，复习要点）
原数组 优化后 遍历顺序 适用场景 dp[i][j] dp[j] 0-1背包：反向；完全背包：正向 只和上一行有关 dp[i][j] dp[i%2][j] 正常 和前两行有关
8.2 状态压缩 DP（★ 提高内容，选学）
思路：当一个维度的状态取值只有 0/1（是/否）时，可以用一个整数的二进制位来表示状态。
典型问题：旅行商问题（TSP）、棋盘覆盖问题。
> GESP 七级不要求掌握状态压缩 DP，但了解思路有助于应对创新题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 练习题推荐
按难度分级
⭐ 入门级（先刷这些）
题号 题名 算法 建议 P1255 跳楼梯 一维 DP 斐波那契变形，必刷 P1048 采药 0-1 背包 背包入门，必刷 P1002 过河卒 二维 DP 理解 DP 边界处理 P1115 最大子段和 一维 DP LIS 基础
⭐⭐ 普及级（巩固提升）
题号 题名 算法 建议 P1616 疯狂的采药 完全背包 和 0-1 背包对比 P1020 导弹拦截 LIS 最长不上升子序列 P1164 小A点菜 背包方案数 DP 方案计数 P1091 合唱队形 LIS LIS + 反向 LIS
⭐⭐⭐ 普及-级（冲刺高分）
题号 题名 算法 建议 P1439 公共子序列 LCS / LCS转LIS 必刷，高频考点 P1775 石子合并 区间 DP 区间 DP 入门 P1833 樱花 混合背包 多种背包综合
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 附录
10.1 GESP 七级 DP 真题考点统计
基于 2023.12 ~ 2025.6 共 7 次考试：
考点 出现次数 题型 难度 0-1 背包 + 滚动数组 4/7 编程题 + 客观题 中等 二维 DP（网格路径/最小路径和） 3/7 编程题 中等 LIS 最长上升子序列 2/7 客观题 中等 LCS 最长公共子序列 1/7 客观题 中高 一维 DP（爬楼梯类） 5/7 客观题 入门 区间 DP 1/7 客观题 中高
10.2 DP 代码模板速查表
算法 状态定义 转移方程 时间复杂度 一维 DP dp[i] 根据题意 O(n) 二维 DP dp[i][j] dp[i][j] = f(dp[i-1][j], dp[i][j-1]) O(nm) 0-1 背包（一维优化） dp[j] dp[j] = max(dp[j], dp[j-w[i]]+v[i]) O(nW)，反向遍历 完全背包 dp[j] dp[j] = max(dp[j], dp[j-w[i]]+v[i]) O(nW)，正向遍历 LIS O(n²) dp[i] dp[i] = max(dp[j]+1), j<i, a[j]<a[i] O(n²) LIS O(n log n)
tail 数组 + 二分 lower_bound O(n log n) LCS dp[i][j] 见第 6 章 O(nm) 区间 DP dp[l][r] 枚举分割点 k O(n³)
10.3 DP 易错点总结
错误 正确做法 典型后果 0-1 背包正向遍历 必须反向 j=W; j>=w[i]; j-- 同一物品被选多次 完全背包反向遍历 必须正向 j=w[i]; j<=W; j++ 物品无法选多次 二维 DP 没初始化边界 dp[0][j] 和 dp[i][0] 要单独初始化 答案错误 LIS 的 lower_bound 用错 严格上升用 lower_bound；非严格用 upper_bound 答案偏大或偏小 区间 DP 枚举顺序错误 区间长度从小到大 用了未计算的小区间 dp 数组开太小 根据题目数据范围开，通常 +5 或 +10 越界 / 段错误 用 int 存大数
LIS/背包方案数可能很大，用 long long 溢出，答案错误 多组数据没清空 dp 每组数据前 memset(dp, 0, sizeof(dp)) 上一组数据干扰
10.4 考试建议
1. 编程题策略：DP 编程题通常比图论简单，争取满分。先想清楚状态定义再写代码。
2. 模板记忆：0-1 背包一维优化模板必须背熟（5 分钟内默写出）。
3. 客观题技巧：
* 给代码片段判断输出 → 手动模拟前几个 dp 值
* 问时间复杂度 → 数循环层数（n² / nm / nW）
* 背包方案判断 → 记住「反向=0-1，正向=完全」
4. 调试技巧：在 DP 循环中 cout << i << " " << j << " " << dp[i][j] << endl; 打印中间结果，帮助理解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 最后提醒：动态规划的核心是「状态定义」。只要 dp[i] 或 dp[i][j] 的含义想清楚了，转移方程往往自然就出来了。多画图、多手动模拟小例子，不要死记模板！
