GESP C++ 六级：线性动态规划专项（一）

核心目标：理解动态规划的基本思想与适用条件，掌握线性 DP 的“状态定义 → 转移方程 → 边界条件 → 遍历顺序”四步法，熟练解决斐波那契、爬楼梯、最长上升子序列、最大子段和、数字三角形等经典线性 DP 问题。
动态规划就是“把大问题拆成小问题，记录小问题的答案，避免重复计算”；线性 DP 的状态是一维或二维的，转移方程沿着一个方向递推；核心是四步：定状态、写方程、找边界、定顺序。

一、考纲定位

根据 CCF 官方考纲，六级知识内容明确要求：“掌握动态规划的基本概念和思想，能够使用动态规划解决线性问题”。动态规划是六级算法模块的核心，也是从“搜索/贪心”迈向“最优化问题”的关键一步。

动态规划在六级考试中的考查分布：

考点	重要程度	典型考法
DP 基本思想与适用条件	★★★★★	选择题高频
状态定义与转移方程		代码填空、编程题
线性 DP（一维）		编程题高频
最长上升子序列 LIS		编程题、程序阅读
最大子段和		编程题
数字三角形	★★★★☆
0/1 背包（一维）	★★★★★
DP 与贪心/递归的区别		选择题

二、动态规划基本概念

2.1 什么是动态规划

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为子问题，记录子问题的解，从而避免重复计算，最终得到原问题最优解的算法。

核心思想：空间换时间。用一个数组（DP 表）存储子问题的答案，当同一个子问题被多次需要时，直接查表，不再重新计算。

直观理解：斐波那契数列的朴素递归是 O(2ⁿ)，因为 fib(5) 会重复计算 fib(3) 很多次。如果用数组记录 fib(3) 的结果，下次直接查表，复杂度就降为 O(n)。

2.2 DP 的两个核心性质

性质	含义	说明
最优子结构	问题的最优解包含子问题的最优解	与贪心共享
重叠子问题	不同的问题分支会重复求解相同的子问题	DP 与分治的核心区别

分治 vs DP：分治的子问题互不重叠（如归并排序的左右两半），DP 的子问题存在重叠（如斐波那契的 fib(n-1) 和 fib(n-2) 都需要 fib(n-3)）。

2.3 DP vs 贪心 vs 递归

对比项	动态规划	贪心	递归
决策方式	保留所有子问题解，统一决策	每步做不可撤销的局部最优	自顶向下分解
核心性质	最优子结构 + 重叠子问题	贪心选择性质 + 最优子结构	终止条件 + 递归式
正确性	状态转移方程保证	需要证明	递归逻辑保证
典型问题	0/1 背包、LIS、最大子段和	区间调度、部分背包	阶乘、汉诺塔
效率	通常 O(n²) 或 O(n)	通常 O(n log n)	可能 O(2ⁿ)

2.4 DP 解题四步法（核心框架）

第一步：定义状态（dp[i] 表示什么）
第二步：写出状态转移方程（dp[i] 怎么从前面推出）
第三步：确定边界条件（dp[0]、dp[1] 等初始值）
第四步：确定遍历顺序（从小到大还是从大到小）

关键原则：状态定义决定了转移方程，转移方程决定了遍历顺序。三者必须一致。

三、线性 DP 基础模型

3.1 斐波那契数列

问题：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)，求 F(n)。

DP 分析：

• 状态：dp[i] 表示第 i 项的值
• 转移：dp[i] = dp[i-1] + dp[i-2]
• 边界：dp[1] = 1, dp[2] = 1
• 顺序：从 3 到 n

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

空间优化：只保留前两个值，空间从 O(n) 降为 O(1)。

int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
}
cout << b << endl;

3.2 爬楼梯

问题：每次可以爬 1 级或 2 级台阶，求爬上 n 级台阶的方案数。

DP 分析：

• 状态：dp[i] 表示爬到第 i 级的方案数
• 转移：dp[i] = dp[i-1] + dp[i-2]（从 i-1 爬 1 级，或从 i-2 爬 2 级）
• 边界：dp[0] = 1, dp[1] = 1
• 顺序：从 2 到 n

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

变体：每次可以爬 1~k 级，转移变为 dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-k]。

3.3 最大子段和

问题：给定一个整数数组，求连续子数组的最大和。

DP 分析：

• 状态：dp[i] 表示以第 i 个元素结尾的最大子段和
• 转移：dp[i] = max(dp[i-1] + a[i], a[i])
• 边界：dp[0] = a[0]
• 答案：max(dp[0], dp[1], ..., dp[n-1])

转移方程的含义：以 a[i] 结尾的最大子段和，要么接在前面的子段后面（dp[i-1] + a[i]），要么自己单独开始（a[i]）。

int dp[1005];
dp[0] = a[0];
int ans = dp[0];
for (int i = 1; i < n; i++) {
    dp[i] = max(dp[i-1] + a[i], a[i]);
    ans = max(ans, dp[i]);
}
cout << ans << endl;

空间优化：只保留前一个 dp 值。

int cur = a[0], ans = a[0];
for (int i = 1; i < n; i++) {
    cur = max(cur + a[i], a[i]);
    ans = max(ans, cur);
}
cout << ans << endl;

3.4 最长上升子序列（LIS）

问题：给定一个数组，求最长上升子序列的长度（子序列不要求连续）。

DP 分析：

• 状态：dp[i] 表示以第 i 个元素结尾的最长上升子序列长度
• 转移：dp[i] = max(dp[j]) + 1，其中 j < i 且 a[j] < a[i]
• 边界：dp[i] = 1（每个元素自身构成长度为 1 的上升子序列）
• 答案：max(dp[0], dp[1], ..., dp[n-1])

int dp[1005];
int ans = 0;
for (int i = 0; i < n; i++) {
    dp[i] = 1;                          // 初始化为 1
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    ans = max(ans, dp[i]);
}
cout << ans << endl;

复杂度：O(n²)，适合 n ≤ 1000。

真题示例：

数组 [10, 9, 2, 5, 3, 7, 101, 18] 的最长上升子序列长度是（ ）。
答案：4（子序列 [2, 3, 7, 101] 或 [2, 5, 7, 101]）。

3.5 数字三角形

问题：给定一个数字三角形，从顶部到底部，每次只能走到左下或右下，求路径上数字之和的最大值。

DP 分析：

• 状态：dp[i][j] 表示从顶部走到第 i 行第 j 列的最大路径和
• 转移：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
• 边界：dp[0][0] = a[0][0]
• 答案：max(dp[n-1][0], ..., dp[n-1][n-1])

int dp[105][105];
dp[0][0] = a[0][0];
for (int i = 1; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        if (j == 0) dp[i][j] = dp[i-1][j] + a[i][j];          // 只能从右上方来
        else if (j == i) dp[i][j] = dp[i-1][j-1] + a[i][j];   // 只能从左上方来
        else dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
    }
}
int ans = 0;
for (int j = 0; j < n; j++) ans = max(ans, dp[n-1][j]);
cout << ans << endl;

空间优化：从下往上递推，可以原地修改，空间 O(n)。

for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        a[i][j] += max(a[i+1][j], a[i+1][j+1]);
    }
}
cout << a[0][0] << endl;

四、0/1 背包问题

4.1 问题描述

有 n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 W。每个物品只能选或不选（0/1），求能装入背包的最大价值。

4.2 二维 DP

• 状态：dp[i][j] 表示前 i 个物品、容量为 j 时的最大价值
• 转移：
  • 不选第 i 个物品：dp[i][j] = dp[i-1][j]
  • 选第 i 个物品（前提 j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
  • 取两者最大值
• 边界：dp[0][j] = 0
• 答案：dp[n][W]

int dp[105][10005];
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
}
cout << dp[n][W] << endl;

4.3 一维 DP（空间优化）

关键：容量 j 必须从大到小遍历，保证每个物品只被选一次。

int dp[10005] = {0};
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]);
    }
}
cout << dp[W] << endl;

为什么从大到小：如果从小到大遍历，dp[j-w[i]] 可能已经包含了第 i 个物品，导致第 i 个物品被选了多次，变成完全背包。

4.4 真题示例

背包容量为 10，物品重量和价值分别为 (5,10)、(4,40)、(6,30)、(3,50)，求最大价值。
答案：90（选物品 2 和 4，重量 4+3=7 ≤ 10，价值 40+50=90）。

五、线性 DP 的解题框架

5.1 四步法应用示例

以“最大子段和”为例：

步骤	内容
定状态	dp[i] 表示以 a[i] 结尾的最大子段和
写方程	dp[i] = max(dp[i-1] + a[i], a[i])
找边界	dp[0] = a[0]
定顺序	i 从 1 到 n-1，正序遍历

5.2 状态定义的常见模式

模式	状态定义	典型问题
以 i 结尾	dp[i] 表示以第 i 个元素结尾的最优解	最大子段和、LIS
前 i 个	dp[i] 表示前 i 个元素的最优解	0/1 背包、线性划分
到达 i	dp[i] 表示到达第 i 个位置的最优解	爬楼梯、跳跃游戏
二维位置	dp[i][j] 表示位置 (i,j) 的最优解	数字三角形、网格路径

六、GESP 六级线性 DP 真题精讲

真题1：最长上升子序列（选择题）

以下代码用于求最长上升子序列，横线处应填入（ ）。

for (int i = 0; i < n; i++) {
 dp[i] = 1;
 for (int j = 0; j < i; j++) {
     if (a[j] < a[i]) {
         ______;
     }
 }
}

A. dp[i] = dp[j] + 1;
B. dp[i] = max(dp[i], dp[j] + 1);
C. dp[j] = dp[i] + 1;
D. dp[i] = max(dp[i], dp[j]);
答案：B

真题2：最大子段和（编程题）

给定 n 个整数，求最大子段和。
输入：-2 1 -3 4 -1 2 1 -5 4
输出：6（子段 [4, -1, 2, 1] 和为 6）

#include <iostream>
using namespace std;

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

    int cur = a[0], ans = a[0];
    for (int i = 1; i < n; i++) {
        cur = max(cur + a[i], a[i]);
        ans = max(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

真题3：0/1 背包（代码填空）

下面代码实现 0/1 背包，横线处应填入（ ）。

for (int i = 1; i <= n; i++) {
 for (int j = W; j >= w[i]; j--) {
     ______;
 }
}

A. dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
B. dp[j] = max(dp[j], dp[j-w[i]]);
C. dp[j] = dp[j-w[i]] + v[i];
D. dp[j] = max(dp[j], dp[j+w[i]] + v[i]);
答案：A

真题4：数字三角形（程序阅读）

给定数字三角形，求从顶部到底部的最大路径和。以下代码的输出是（ ）。

for (int i = n - 2; i >= 0; i--)
 for (int j = 0; j <= i; j++)
     a[i][j] += max(a[i+1][j], a[i+1][j+1]);
cout << a[0][0] << endl;

答案：从下往上递推，a[0][0] 即为最大路径和。

七、易错点汇总

1. 状态定义不明确：dp[i] 到底表示“以 i 结尾”还是“前 i 个”，必须想清楚。
2. 转移方程遗漏情况：如 LIS 中忘记 dp[i] = 1 的初始化，或最大子段和忘记“重新开始”的选项。
3. 边界条件写错：dp[0] 还是 dp[1] 作为起点，取决于状态定义。
4. 遍历顺序错误：0/1 背包一维优化必须从大到小遍历容量，否则变成完全背包。
5. 答案位置错误：最大子段和的答案不是 dp[n-1]，而是 max(dp[0..n-1])。
6. DP 数组未初始化：全局数组默认 0，局部数组需要手动初始化。
7. 空间优化时变量更新顺序错误：如斐波那契的 a = b; b = c; 顺序不能乱。
8. 整数溢出：大数 DP 用 long long。
9. 混淆 DP 与贪心：0/1 背包不能用贪心，必须用 DP。
10. 数字三角形边界处理：j == 0 和 j == i 时需要特判，不能直接取 max(dp[i-1][j-1], dp[i-1][j])。

八、速查表

模型	状态定义	转移方程	边界	答案
斐波那契	dp[i] 第 i 项	dp[i]=dp[i-1]+dp[i-2]	dp[1]=dp[2]=1	dp[n]
爬楼梯	dp[i] 到第 i 级方案数		dp[0]=dp[1]=1
最大子段和	dp[i] 以 i 结尾	dp[i]=max(dp[i-1]+a[i], a[i])	dp[0]=a[0]	max(dp)
LIS		dp[i]=max(dp[j])+1, a[j]<a[i]	dp[i]=1
数字三角形	dp[i][j] 到 (i,j)	dp[i][j]=max(左上,右上)+a[i][j]	dp[0][0]=a[0][0]	max(dp[n-1])
0/1 背包（二维）	dp[i][j] 前 i 个容量 j	dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v)	dp[0][j]=0	dp[n][W]
0/1 背包（一维）	dp[j] 容量 j	dp[j]=max(dp[j], dp[j-w]+v)	dp[j]=0	dp[W]

九、总结

线性动态规划是 GESP 六级算法模块的核心内容。记住十句话：

1. 动态规划的核心是“记录子问题答案，避免重复计算”，空间换时间。
2. DP 的两个核心性质：最优子结构 + 重叠子问题。
3. DP 四步法：定状态 → 写方程 → 找边界 → 定顺序。
4. 状态定义决定了转移方程和遍历顺序，三者必须一致。
5. 最大子段和的状态是“以 i 结尾”，答案是 max(dp) 不是 dp[n-1]。
6. LIS 的状态也是“以 i 结尾”，转移需要遍历前面所有 j < i。
7. 0/1 背包一维优化必须从大到小遍历容量，否则变成完全背包。
8. 数字三角形可以从下往上递推，空间优化为 O(n)。
9. DP 与贪心的核心区别：贪心每步做不可撤销的选择，DP 保留所有子问题解。
10. 多练“最大子段和”“LIS”“数字三角形”“0/1 背包”四类题。

复习建议：先把斐波那契和爬楼梯的 DP 写法与空间优化写熟；再重点攻克最大子段和与 LIS，理解“以 i 结尾”的状态定义；然后掌握 0/1 背包的二维和一维写法，牢记“从大到小”的原因；最后练习数字三角形的两种递推方向。考试中先判断题目属于哪种模型，再套用对应的状态定义和转移方程，最后检查边界和遍历顺序。