【GESP】C++六级考试大纲知识点梳理, (5) 动态规划与背包问题

GESP C++六级官方考试大纲中，第5条考点标志着我们正式跨入了“算法设计”的深水区——动态规划。

（5）掌握简单动态规划的算法思想，能够使用代码解决相应的一维动态规划问题和简单背包问题。 {: .prompt-info}

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。 {: .prompt-warning}

动态规划（Dynamic Programming，简称 DP）往往是初学者最头疼的拦路虎。很多同学觉得它玄之又玄，状态转移方程像天书一样。其实，DP 的核心思想非常朴素，就是“拒绝重复劳动”。本文将带你拆解 DP 的套路，并攻克一维 DP 和经典的背包问题。 {: .prompt-info}

六级考点系列：

• 【GESP】C++六级考试大纲知识点梳理, (1) 树的概念与遍历
• 【GESP】C++六级考试大纲知识点梳理, (2) 哈夫曼树、完全二叉树与二叉排序树
• 【GESP】C++六级考试大纲知识点梳理, (3) 哈夫曼编码与格雷码
• 【GESP】C++六级考试大纲知识点梳理, (4) 搜索算法 {: .prompt-tip}

一、什么是动态规划 (DP)？

动态规划 (Dynamic Programming) 是一种解决复杂问题的算法思想。它将一个大问题分解成若干个相互重叠的子问题，并通过 存储（记忆化） 每个子问题的解，避免重复计算，从而提高效率。

简单来说，DP 的核心就是：分而治之，并记住你做过的事情。 当下次遇到相同的小问题时，直接查“备忘录”，而不是重新计算一遍。

1.1 从斐波那契数列说起

大家都很熟悉斐波那契数列：$f(n) = f(n-1) + f(n-2)$。如果我们用递归直接写：

int f(int n) {
    if (n <= 2) return 1;
    return f(n-1) + f(n-2);
}

这有什么问题？大量的重复计算！

计算 $f(5)$ 需要 $f(4)$ 和 $f(3)$；而计算 $f(4)$ 又需要 $f(3)$ 和 $f(2)$。你看，$f(3)$ 被算了两次！当 $n$ 变大时，这种重复会呈指数级爆炸。

动态规划的智慧：

既然 $f(3)$ 算过了，为什么不把它记下来呢？下次再需要 $f(3)$，直接查表，不用再算一遍。

这就是 DP 的核心：记忆化 (Memoization) 或 表格法 (Tabulation)。

• 大问题拆解：把复杂问题拆成一个个子问题。
• 记录答案：每个子问题只算一次，算完存起来。
• 查表复用：需要时直接取用，拒绝重复劳动。

1.2 DP 解题三部曲

做 DP 题，心里要有这三步：

1. 定义状态 (DP 数组的含义)

dp[i] 代表什么？（例如：走到第 i 级台阶的方法数、前 i 个物品的最大价值等）

2. 找状态转移方程 (递推公式)

dp[i] 怎么由前面的 dp[i-1]、dp[i-2] 推导出来？（例如：$dp[i] = dp[i-1] + dp[i-2]$）

3. 确定边界条件 (初始化)

也就是“多米诺骨牌”的第一张牌。（例如：$dp[0]=0, dp[1]=1$）

二、一维动态规划实战：爬楼梯

2.1 题目描述

假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。 每次你可以爬 $1$ 或 $2$ 个台阶。 你有多少种不同的方法可以爬到楼顶呢？

2.2 三部曲分析

1. 定义状态：

dp[i] 表示到达第 i 阶楼顶的方法总数。

2. 状态转移：

想要到达第 i 阶，只有两种可能：

• 从第 i-1 阶跨 1 步上来。
• 从第 i-2 阶跨 2 步上来。

所以：$dp[i] = dp[i-1] + dp[i-2]$ (这不就是斐波那契数列吗？是的，很多简单 DP 本质就是递推)

3. 边界条件：

• dp[1] = 1 (只有一种跳法：1)
• dp[2] = 2 (两种跳法：1+1 或 2)

2.3 代码实现

#include <iostream>
#include <vector>

int climbStairs(int n) {
    if (n <= 2) return n;

    // 1. 定义 DP 数组
    std::vector<int> dp(n + 1);

    // 2. 初始化边界
    dp[1] = 1;
    dp[2] = 2;

    // 3. 开始递推 (从小到大)
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
    }

    return dp[n];
}

三、背包问题 (Knapsack Problem)

背包问题是动态规划中最经典的模型。在六级考试中，主要考察最基础的0/1 背包问题。

3.1 什么是 0/1 背包？

问题描述：你有一个背包，最大载重为 $W$。商店里有 $N$ 件物品，第 $i$ 件物品的重量是 $w[i]$，价值是 $v[i]$。每件物品只有一件，你只能选择 “拿” 或者 “不拿”（这就是 0/1 的含义，不能切开拿一半）。 目标：在不超过背包载重的前提下，让包里物品的总价值最大。

3.2 0/1 背包的二维解法 (理解原理)

1. 状态定义：

dp[i][j] 表示：当我们只考虑前 i 件物品（也就是从第 1 件到第 i 件物品），并且背包的最大容量是 j 时，我们能够装入背包的物品的总价值最大是多少。

例如：如果 dp[2][5] 的值为 12，就代表当我们只在物品 1 和物品 2 之间做选择，并且背包最多只能装下 5 单位重量时，我们能得到的最高总价值是 12。

2. 状态转移：对于第 i 件物品，我们面临两个选择：

• 不拿：那就只能指望前 i-1 件物品，且背包容量 j 没变。$\rightarrow dp[i-1][j]$
• 拿：前提是背包得装得下（$j \ge w[i]$）。如果拿了，价值增加 $v[i]$，背包容量剩下 $j - w[i]$，剩下的容量留给前 i-1 件物品去发挥。$\rightarrow dp[i-1][j - w[i]] + v[i]$

我们要取两者的最大值：

二维数组代码实现 (便于理解但耗内存)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 105;
const int MAX_W = 1005;

int w[MAX_N], v[MAX_N];
int dp[MAX_N][MAX_W]; // 定义在全局，自动初始化为 0

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

    // 外层枚举物品 (i 从 1 到 N)
    for (int i = 1; i <= N; i++) {
        // 内层枚举容量 (j 从 0 到 W)
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                // 装不下，只能继承上一轮的值 (相当于不拿)
                dp[i][j] = dp[i-1][j];
            } else {
                // 能装下，在“不拿”和“拿”之间选最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}

3.3 一维优化 (滚动数组 - 考试推荐)

1. 为什么一定要优化？（算笔账）

假设题目给出 $N=5000$（物品数），$W=20000$（载重）。

• 二维方案 (dp[5000][20000])：需要 1 亿个 int，占用约 400 MB 内存。考试通常限制 128 MB，直接 爆内存 (MLE)。
• 一维方案 (dp[20000])：只需要 2 万个 int，占用约 80 KB 内存。非常安全。

2. 优化思路：一块黑板擦了写

观察二维公式：dp[i][j] 的值只依赖于 dp[i-1][...]（也就是上一行）的值。 我们可以把 dp 数组看作唯一的一块黑板。

• 第 1 轮：在黑板上计算并写下处理完“物品 1”后的结果。
• 第 2 轮：直接在这块黑板上修改数据，计算“物品 2”的结果。

新公式：

• 等号左边的 dp[j]：新数据（当前正在计算的，相当于第 i 行）。
• 等号右边的 dp[j] 和 dp[j-w]：我们希望读取到的是旧数据（黑板上原本写的，相当于第 i-1 行）。

3. 核心难点：要倒序遍历

既然是在同一块黑板上“擦了写”，就存在一个先后顺序问题。

假设场景：

黑板上写的全是 0（初始状态）。现在我们要处理 物品 i：重量 $w=1$，价值 $v=2$。

❌ 错误演示：从左往右写 (正序 $j: 1 \rightarrow 2$)

我们要计算 dp[1] 和 dp[2]。

问题出在哪？ 当我们算 dp[2] 时，我们需要的是旧的 dp[1]（应该是 0）。 但因为是从左往右算，dp[1] 已经被 Step 1 覆盖成新的 2 了。我们用新数据推导新数据，导致物品被重复计算。

✅ 正确演示：从右往左写 (倒序 $j: 2 \rightarrow 1$)

结论： 倒序遍历 保证了我们在计算 dp[j] 时，它左边的 dp[j-w] 还没有被修改，依然是上一轮留下的旧数据。这就完美模拟了二维数组中“读取上一行”的效果。

4. 一维优化代码模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_W = 1005; // 只需要定义最大容量
int dp[MAX_W];          // 一维数组

int main() {
    int N, W;
    cin >> N >> W;

    // 两个循环嵌套：
    // 1. 外层枚举物品 (i 从 1 到 N)
    // 2. 内层枚举容量 (j 从 W 到 w[i]) -> 必须倒序！

    for (int i = 1; i <= N; i++) {
        int w, v; // 可以边读边算，连 w[], v[] 数组都省了
        cin >> w >> v;

        // 倒序遍历：从背包最大容量 W 开始，直到放不下当前物品为止
        for (int j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

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

四、总结与技巧

💡 核心思想辨析：DP vs 递归 你可能会觉得：“DP 的公式 $f(n) = f(n-1) + f(n-2)$ 不就是递归吗？” 没错，数学逻辑是一样的，但执行效率天差地别：

• 普通递归 (暴力)：像是健忘的人。问他 $f(3)$ 等于几，他算一遍；过一会为了算 $f(4)$ 又问他 $f(3)$，他忘记自己算过了，又重新算一遍。这会导致大量重复计算。
• DP (动态规划)：像是带备忘录的人。算出 $f(3)$ 后，他立马记在纸上（DP 数组）。下次再需要 $f(3)$，他直接看纸，绝不重复劳动。
• 总结：DP 本质上就是 “拒绝重复计算的递归”（通常通过自底向上填表来实现）。

备考建议：

1. 不要死记代码，要理解 dp 数组每个格子的含义。
2. 画表辅助：初学时，在纸上画出二维表格，模拟填表过程，能极快帮助理解。
3. 区分 0/1 背包与完全背包：0/1 背包内层倒序，完全背包（每种物品无限取）内层正序。虽然六级重点是 0/1，但了解区别有助于防止写错。