GESP C++ 七级 · 动态规划

энтджей

2026-05-12 20:30:58

发布于：浙江

9阅读

0回复

0点赞

适用对象：准备 GESP C++ 七级考试的学生（建议已掌握一维 DP，正在学习二维 DP）
模块权重：约 11%（编程题第二大来源，仅次于图论）
编程题命中率：每次考试大概率出现一道 DP 题（背包 / 二维 DP / LIS）
版本：2026.05 更新，基于 2023.12 ~ 2025.6 共 7 次真题分析

1. 动态规划基础概念

1.1 什么是动态规划？

生活类比：你站在楼梯底部，每次可以爬 1 级或 2 级台阶，问爬到第 n 级台阶有多少种不同的方法？

台阶:  0  1  2  3  4  5
       │  │  │  │  │  │
       出发     到达

要想到达第 5 级，只能从第 4 级走 1 步，或从第 3 级走 2 步。
所以：f(5) = f(4) + f(3)

同理：f(4) = f(3) + f(2)
      f(3) = f(2) + f(1)
      f(2) = f(1) + f(0) = 1 + 1 = 2
      f(1) = 1（只有 1 种方法：走 1 步）
      f(0) = 1（站在地面，也算 1 种）

→ f(5) = f(4) + f(3) = 5 + 3 = 8 种

这就是动态规划的核心思想：

把大问题拆成小问题，把小问题的答案存起来，避免重复计算。

1.2 动态规划的两个关键性质

性质	说明	例子
最优子结构	大问题的最优解，包含小问题的最优解	最短路径问题：A→C 的最短路，一定包含 A→B 的最短路
重叠子问题	计算过程中，同一个子问题会被反复用到	斐波那契：f(5) 和 f(4) 都要算 f(3)，算两次浪费

1.3 动态规划的解题步骤

四步走：

第 1 步：定义状态
        → dp[i] 或 dp[i][j] 表示什么？
        
第 2 步：写出状态转移方程
        → dp[i] 和哪些更小的 dp 有关系？
        
第 3 步：确定边界条件
        → dp[0]、dp[1] 等初始值是多少？
        
第 4 步：确定计算顺序
        → 从小到大？从大到小？按什么顺序填表？

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)。

❌ 错误写法（递归，会超时）

// 这个写法在 n=50 时会非常慢！
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 大量重复计算
}

问题分析：f(5) 要算 f(4)+f(3)，f(4) 又要算 f(3)+f(2)……f(3) 被算了两次！

递归树（f(5)）：
                    f(5)
                   /    \
                f(4)    f(3)
               /    \    /    \
            f(3)  f(2) f(2) f(1)
           /    \
        f(2)  f(1)

→ f(3) 算了 2 次，f(2) 算了 3 次……

✅ 正确写法一：记忆化搜索（自顶向下）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100005;
long long memo[N]; // 记忆数组：memo[i] 已经算过了就直接返回

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // 算过了，直接返回！
    memo[n] = fib(n-1) + fib(n-2);    // 没算过，算一遍
    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(memo)); // 初始化为 -1（表示没算过）
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

✅ 正确写法二：递推（自底向上，推荐！）

#include <iostream>
using namespace std;

const int N = 100005;
long long dp[N];

int main() {
    int n;
    cin >> n;

    // 边界条件
    dp[0] = 0;
    dp[1] = 1;

    // 递推填表（从小到大）
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;
    return 0;
}

为什么递推（写法二）更好？

没有递归调用，不会栈溢出

代码更简单

速度更快（没有函数调用开销）
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] 种方法

代码模板：

#include <iostream>
using namespace std;

const int N = 100005;
long long dp[N];

int main() {
    int n;
    cin >> n;

    // 边界条件（注意：dp[0] 根据问题定义，通常是 1）
    dp[0] = 1; // 站在地面，1 种方法（不走）
    dp[1] = 1; // 第 1 级，只能从地面走 1 步

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;
    return 0;
}

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])

要么自己单独开头（不要前面的）
要么接在前面的最大子数组后面

代码模板：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // dp[i] = 以 a[i] 结尾的最大子数组和
    vector<long long> dp(n+1);
    long long ans = a[1]; // 答案至少是第一个数

    dp[1] = a[1]; // 边界
    for (int i = 2; i <= n; i++) {
        dp[i] = max((long long)a[i], dp[i-1] + a[i]);
        ans = max(ans, dp[i]); // 更新全局答案
    }

    cout << ans << endl;
    return 0;
}

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) 有多少种不同的路径？

3×2 网格：

  (0,0) → (0,1) → (0,2)
    ↓        ↓        ↓
  (1,0) → (1,1) → (1,2)

从 (0,0) 到 (1,2) 的所有路径：
  1. 右→右→下
  2. 右→下→右
  3. 下→右→右
  → 共 3 种

思路分析

状态定义：dp[i][j] = 从 (0,0) 走到 (i,j) 的路径数

状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]
             ↑              ↑
           从上面走来      从左边走来

边界条件：

第一行：只能从左边来 → dp[0][j] = 1
第一列：只能从上面来 → dp[i][0] = 1

代码模板

#include <iostream>
using namespace std;

const int N = 105;
long long dp[N][N]; // 注意用 long long，路径数可能很大

int main() {
    int m, n;
    cin >> m >> n; // m 行，n 列

    // 边界条件
    for (int i = 0; i < m; i++) dp[i][0] = 1; // 第一列
    for (int j = 0; j < n; j++) dp[0][j] = 1; // 第一行

    // 递推填表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    cout << dp[m-1][n-1] << endl;
    return 0;
}

3.3 带障碍的网格路径

问题升级：网格中某些格子有障碍（不能走），求路径数。

关键变化：遇到障碍格时，dp[i][j] = 0（没有路径能到达这里）。

#include <iostream>
using namespace std;

const int N = 105;
int grid[N][N];     // grid[i][j] = 1 表示障碍
long long dp[N][N];

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];

    // 起点是障碍，直接返回 0
    if (grid[0][0] == 1) {
        cout << 0 << endl;
        return 0;
    }

    dp[0][0] = 1; // 起点

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0; // 障碍格，路径数为 0
                continue;
            }
            // 注意：这里不能简单地写 i>0 和 j>0 分别加
            // 因为 (0,0) 已经被初始化了
            if (i > 0) dp[i][j] += dp[i-1][j];
            if (j > 0) dp[i][j] += dp[i][j-1];
        }
    }

    cout << dp[m-1][n-1] << endl;
    return 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])

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 205;
const int INF = 0x3f3f3f3f;
int grid[N][N];
int dp[N][N];

int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];

    // 初始化 dp 为大数
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = INF;

    dp[0][0] = grid[0][0];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i > 0)
                dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j]);
            if (j > 0)
                dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j]);
        }
    }

    cout << dp[m-1][n-1] << endl;
    return 0;
}

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 的含义），问背包能装下的物品的最大总价值是多少？

例子：
背包容量 W = 10
物品： 重量  价值
  1      3     4
  2      4     5
  3      5     6

最佳方案：选物品 1 和 2，总重量 3+4=7，总价值 4+5=9

4.2 标准二维 DP 解法

状态定义：dp[i][j] = 考虑前 i 件物品，背包容量为 j 时，能获得的最大价值

状态转移方程：

dp[i][j] = max(
    dp[i-1][j],                  // 不选第 i 件物品
    dp[i-1][j-w[i]] + v[i]      // 选第 i 件物品（需要容量够）
)

边界条件：dp[0][j] = 0（不考虑任何物品时，价值为 0）

代码模板（二维，好理解）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1005;
int w[N], v[N];      // w[i]=重量, v[i]=价值
int dp[N][N];       // dp[i][j]

int main() {
    int n, W;
    cin >> n >> W; // n=物品数, W=背包容量
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // dp[0][j] = 0 已经默认初始化了

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            // 不选第 i 件（继承上一行）
            dp[i][j] = dp[i-1][j];

            // 选第 i 件（需要容量够）
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
            }
        }
    }

    cout << dp[n][W] << endl;
    return 0;
}

4.3 滚动数组优化（★ 高频考点！）

问题：二维数组 dp[1005][1005] 占用约 4MB 内存，如果 n 和 W 都很大（如 10⁵），会内存超限！

优化思路：dp[i][...] 只和 dp[i-1][...] 有关，不需要存所有行，只需要「上一行」和「当前行」。

更进一步的优化：只用一行数组！但遍历顺序必须反过来（从 W 到 w[i]）。

为什么反过来？
假设：    j:  0  1  2  3  4
       dp: [0, 0, 0, 0, 0]
       当前物品重量 w[i]=2, 价值 v[i]=3

如果正向遍历 (j=0→W):
  j=2: dp[2] = max(dp[2], dp[0]+3) = 3  ✓
  j=3: dp[3] = max(dp[3], dp[1]+3) = 3  ✓
  j=4: dp[4] = max(dp[4], dp[2]+3) = 6  ✗  (dp[2] 已经被更新了！)

如果反向遍历 (j=W→w[i]):
  j=4: dp[4] = max(dp[4], dp[2]+3) = 3  ✓ (dp[2] 还是上一轮的值)
  j=3: dp[3] = max(dp[3], dp[1]+3) = 3  ✓
  j=2: dp[2] = max(dp[2], dp[0]+3) = 3  ✓
  → 正确！每个物品只被选了一次

代码模板（一维优化版，考试推荐！）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1005;
int w[N], v[N];
int dp[N]; // 一维数组！

int main() {
    int n, W;
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // 初始化（求最大值时，dp 数组默认就是 0，可以省略）
    // memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        // 关键：反向遍历！
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
        // 注意：j < w[i] 的情况，dp[j] 不变（不选这件物品）
    }

    cout << dp[W] << endl;
    return 0;
}

记忆口诀：

0-1 背包：容量反向遍历（j = W; j >= w[i]; j--）

完全背包（每件物品可选无限次）：容量正向遍历（j = w[i]; j <= W; j++）

4.4 完全背包问题（对比学习）

区别：0-1 背包每件物品只能选一次，完全背包每件物品可以选无限次。

// 完全背包：正向遍历（和 0-1 背包的唯一区别！）
for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= W; j++) {  // 正向！
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

4.5 背包问题练习题推荐

题号	题名	难度	类型	训练要点
P1048	采药	⭐ 入门	0-1 背包	背包入门、一维优化
P1616	疯狂的采药	⭐⭐ 普及	完全背包	完全背包、大容量
P1049	装箱问题	⭐ 入门	0-1 背包（变种）	背包求能否装满
P1833	樱花	⭐⭐⭐ 普及-	混合背包	0-1 + 完全 + 多重
P1164	小A点菜	⭐⭐ 普及	0-1 背包（方案数）	方案计数型 DP

5. LIS 最长上升子序列

5.1 概念讲解

问题：给一个数组，找出一个子序列（不一定连续），使得这个子序列是严格上升的，且长度最长。

数组: [10, 9, 2, 5, 3, 7, 101, 18]

所有上升子序列中，最长的是：
  [2, 3, 7, 101]    长度 = 4
  [2, 5, 7, 101]    长度 = 4
  [2, 3, 7, 18]     长度 = 4
  [2, 5, 7, 18]     长度 = 4
  → 答案 = 4

5.2 O(n²) DP 解法（好理解，适合入门）

状态定义：dp[i] = 以第 i 个数结尾的最长上升子序列的长度

状态转移方程：

dp[i] = max(dp[j] + 1)  其中 j < i 且 a[j] < a[i]
                   ↑
         在 i 之前找一个比 a[i] 小的数，
         把它后面接上 a[i]，长度 +1

边界条件：每个数自己构成一个长度为 1 的子序列 → dp[i] = 1

代码模板（O(n²)）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1005;
int a[N], dp[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int ans = 1; // 至少有一个数

    for (int i = 1; i <= n; i++) {
        dp[i] = 1; // 边界：自己构成长度为 1 的子序列
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) { // 可以接在 a[j] 后面
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]); // 更新全局答案
    }

    cout << ans << endl;
    return 0;
}

时间复杂度：O(n²)，n ≤ 1000 时可以用。

5.3 O(n log n) 优化解法（★ GESP 高频！）

思路：维护一个数组 tail，tail[k] 表示「长度为 k 的上升子序列的最小结尾值」。

数组: [10, 9, 2, 5, 3, 7, 101, 18]

处理过程：
  i=1: a[1]=10  → tail = [10]           (长度1的最小结尾是10)
  i=2: a[2]=9   → tail = [9]           (长度1的最小结尾改为9，更小！)
  i=3: a[3]=2   → tail = [2]           (长度1的最小结尾改为2)
  i=4: a[4]=5   → tail = [2, 5]       (可以接在2后面，长度变为2)
  i=5: a[5]=3   → tail = [2, 3]       (长度2的最小结尾改为3，更小！)
  i=6: a[6]=7   → tail = [2, 3, 7]    (可以接在3后面，长度变为3)
  i=7: a[7]=101 → tail = [2, 3, 7, 101] (可以接在7后面，长度变为4)
  i=8: a[8]=18  → tail = [2, 3, 7, 18]  (长度4的最小结尾改为18，更小！)

最终 tail 的长度 = 4 = LIS 长度

关键操作：在 tail 数组中用二分查找找到第一个 ≥ a[i] 的位置，用 a[i] 替换它。

代码模板（O(n log n)，推荐掌握！）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // tail[i] = 长度为 i+1 的 LIS 的最小结尾值
    // len = 当前 LIS 的长度
    vector<int> tail;

    for (int i = 0; i < n; i++) {
        // 在 tail 中找第一个 >= a[i] 的位置
        auto it = lower_bound(tail.begin(), tail.end(), a[i]);

        if (it == tail.end()) {
            // a[i] 比 tail 中所有数都大，可以接在后面
            tail.push_back(a[i]);
        } else {
            // 用 a[i] 替换第一个 >= 它的数（让结尾更小）
            *it = a[i];
        }
    }

    cout << tail.size() << endl; // tail 的长度 = LIS 长度
    return 0;
}

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 概念讲解

问题：给两个字符串（或数组），找一个子序列（不一定连续），它同时是这两个字符串的子序列，且长度最长。

字符串 1: A  B  C  B  D  A  B
字符串 2: B  D  C  A  B  A

最长公共子序列：BCBA（或 BDAB），长度 = 4

子序列 vs 子串：

子序列：不一定连续（可以跳过某些字符）

子串：必须连续
LCS 找的是子序列！

6.2 状态定义与转移方程

状态定义：dp[i][j] = 字符串1的前 i 个字符和字符串2的前 j 个字符的 LCS 长度

状态转移方程：

如果 s1[i-1] == s2[j-1]（当前字符相同）：
    dp[i][j] = dp[i-1][j-1] + 1
否则（当前字符不同）：
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

边界条件：dp[0][j] = 0，dp[i][0] = 0（空串和任何串的 LCS 长度为 0）

6.3 代码模板

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 1005;
int dp[N][N]; // dp[i][j]
string s1, s2;

int main() {
    cin >> s1 >> s2;
    int n = s1.length(), m = s2.length();

    // dp[0][*] 和 dp[*][0] 默认就是 0，可以省略初始化

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1]) {
                // 当前字符相同，可以同时选
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // 当前字符不同，舍弃其中一个
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

时间复杂度：O(nm)，n 和 m 都在 1000 以内可以用。

6.4 LCS 练习题推荐

题号	题名	难度	训练要点
P1439	公共子序列	⭐⭐⭐ 普及-	LCS 标准模板
P1000	豆腐块	⭐⭐ 普及	LCS 思想应用

7. 区间动态规划

7.1 概念讲解

区间 DP 的状态定义是「区间」[l, r]，即：考虑从位置 l 到位置 r 这个区间的最优解。

典型问题：石子合并。

7.2 石子合并问题

问题：有 n 堆石子排成一排，每次可以合并相邻的两堆，合并的代价是两堆石子的总数。问把所有石子合并成一堆的最小总代价是多少？

例子：4 堆石子，石子数分别为 [1, 2, 3, 4]

合并方案：
  方案1: ((1+2)+3)+4 = 3+6+10 = 19
  方案2: (1+2)+(3+4) = 3+7    = 10  ← 最优！
  方案3: 1+(2+(3+4)) = 3+7+10 = 20

→ 答案 = 10

状态定义：dp[l][r] = 合并第 l 堆到第 r 堆石子所需的最小代价

状态转移方程：

dp[l][r] = min(dp[l][k] + dp[k+1][r]) + sum(l,r)
                 ↑              ↑
           把 [l,r] 分成两部分  合并这两部分的代价
           枚举分割点 k

关键：需要先计算小区间，再计算大区间 → 区间长度从小到大枚举！

代码模板

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 305;
const int INF = 0x3f3f3f3f;
int a[N];
int sum[N];   // 前缀和：sum[i] = a[1]+a[2]+...+a[i]
int dp[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i]; // 前缀和
    }

    // 初始化 dp 为大数
    memset(dp, 0x3f, sizeof(dp));

    // 边界：合并一堆石子，代价为 0
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }

    // 枚举区间长度 len（从 2 开始，因为长度为 1 已经初始化了）
    for (int len = 2; len <= n; len++) {
        // 枚举区间起点 l
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1; // 区间终点

            // 枚举分割点 k
            for (int k = l; k < r; k++) {
                // sum[r] - sum[l-1] = a[l]+a[l+1]+...+a[r]
                int cost = sum[r] - sum[l-1];
                dp[l][r] = min(dp[l][r],
                                dp[l][k] + dp[k+1][r] + cost);
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

时间复杂度：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 考试建议

编程题策略：DP 编程题通常比图论简单，争取满分。先想清楚状态定义再写代码。
模板记忆：0-1 背包一维优化模板必须背熟（5 分钟内默写出）。
客观题技巧：
- 给代码片段判断输出 → 手动模拟前几个 dp 值
- 问时间复杂度 → 数循环层数（n² / nm / nW）
- 背包方案判断 → 记住「反向=0-1，正向=完全」
调试技巧：在 DP 循环中 cout << i << " " << j << " " << dp[i][j] << endl; 打印中间结果，帮助理解。

最后提醒：动态规划的核心是「状态定义」。只要 dp[i] 或 dp[i][j] 的含义想清楚了，转移方程往往自然就出来了。多画图、多手动模拟小例子，不要死记模板！

有帮助，赞一个

去预览

0/2000

这里空空如也

目录

1. 动态规划基础概念

1.1 什么是动态规划？

1.2 动态规划的两个关键性质

1.3 动态规划的解题步骤

1.4 动态规划 vs 分治 vs 贪心

2. 一维动态规划

2.1 斐波那契数列（DP 入门）

❌ 错误写法（递归，会超时）

✅ 正确写法一：记忆化搜索（自顶向下）

✅ 正确写法二：递推（自底向上，推荐！）

2.2 爬楼梯问题

2.3 最大子数组和

2.4 一维 DP 练习题推荐

3. 二维动态规划

3.1 概念讲解

3.2 网格路径问题

思路分析

代码模板

3.3 带障碍的网格路径

3.4 最小路径和

3.5 二维 DP 练习题推荐

4. 0-1 背包问题

4.1 概念讲解

4.2 标准二维 DP 解法

代码模板（二维，好理解）

4.3 滚动数组优化（★ 高频考点！）

代码模板（一维优化版，考试推荐！）

4.4 完全背包问题（对比学习）

4.5 背包问题练习题推荐

5. LIS 最长上升子序列

5.1 概念讲解

5.2 O(n²) DP 解法（好理解，适合入门）

代码模板（O(n²)）

5.3 O(n log n) 优化解法（★ GESP 高频！）

代码模板（O(n log n)，推荐掌握！）

5.4 LIS 练习题推荐

6. LCS 最长公共子序列

6.1 概念讲解

6.2 状态定义与转移方程

6.3 代码模板

6.4 LCS 练习题推荐

7. 区间动态规划

7.1 概念讲解

7.2 石子合并问题

代码模板

7.3 区间 DP 要点

7.4 区间 DP 练习题推荐

8. DP 优化技巧

8.1 滚动数组（已讲，复习要点）

8.2 状态压缩 DP（★ 提高内容，选学）

9. 练习题推荐

按难度分级

⭐ 入门级（先刷这些）

⭐⭐ 普及级（巩固提升）

⭐⭐⭐ 普及-级（冲刺高分）

10. 附录

10.1 GESP 七级 DP 真题考点统计

10.2 DP 代码模板速查表

10.3 DP 易错点总结

10.4 考试建议

热门讨论