第5章简单动态规划

🎯 本章学习目标

通过本章的学习，你将能够：

理解DP思想：掌握动态规划的核心——最优子结构和重叠子问题
掌握DP四步走：定状态、找转移、定初始、定顺序
熟练一维DP：掌握爬楼梯、最大子段和等经典一维DP问题
掌握01背包：理解01背包的状态转移方程和空间优化
掌握完全背包：理解完全背包与01背包的区别
理解数字三角形：掌握二维DP的基本思路
区分贪心与DP：清楚什么时候用贪心，什么时候用DP
空间优化技巧：掌握滚动数组等空间优化方法
分析DP复杂度：能计算DP的时间和空间复杂度
应对真题题型：能解决选择、判断、编程等各类DP题目

🗺️ 本章知识图谱

简单动态规划
├── DP 基础概念
│   ├── 两个核心要素
│   │   ├── 最优子结构
│   │   └── 重叠子问题
│   ├── DP vs 贪心
│   │   ├── 贪心：局部最优即全局最优
│   │   └── DP：枚举所有选择，取最优
│   └── DP 解题四步
│       ├── 1. 定状态（dp数组含义）
│       ├── 2. 找转移（状态转移方程）
│       ├── 3. 定初始（边界条件）
│       └── 4. 定顺序（计算顺序）
├── 一维 DP
│   ├── 爬楼梯（斐波那契型）
│   │   ├── dp[i] = dp[i-1] + dp[i-2]
│   │   └── 初始：dp[1]=1, dp[2]=2
│   ├── 最大子段和
│   │   ├── dp[i] = max(dp[i-1]+a[i], a[i])
│   │   └── 结果 = max(dp[i])
│   └── 打家劫舍（了解）
├── 二维 DP
│   └── 数字三角形
│       ├── dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j])
│       └── 边界：每行第一个和最后一个
├── 背包问题
│   ├── 01 背包
│   │   ├── 状态：dp[i][j] = 前i个物品装容量j的最大价值
│   │   ├── 转移：选或不选第i个
│   │   ├── dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
│   │   ├── 空间优化：一维数组，j从大到小（逆序）
│   │   └── 逆序原因：防止物品被重复选
│   └── 完全背包
│       ├── 每个物品可以选无限次
│       ├── 空间优化：一维数组，j从小到大（顺序）
│       └── 顺序原因：物品可以重复选
└── 空间优化
    ├── 滚动数组（用前一行就行）
    └── 背包一维化

一、动态规划基础回顾

1.1 什么是动态规划？

动态规划（Dynamic Programming，简称 DP）是一种通过将原问题分解为相互重叠的子问题，并保存子问题的解来避免重复计算的算法思想。

一句话概括：把大问题拆成小问题，记住小问题的答案，用它拼出大问题的答案。

1.2 DP 适用条件

一个问题能用 DP 求解，需要满足两个关键性质：

性质	含义	通俗理解
最优子结构	大问题的最优解包含子问题的最优解	"好的答案由好的小答案组成"
重叠子问题	不同分支的子问题会反复出现	"同一个小问题会被算很多遍"

⚠️ 高频易错点：很多同学分不清 DP 和贪心的区别。贪心只看眼前最优，DP 会考虑全局最优。当"局部最优不能推导出全局最优"时，贪心就失效了，此时应该想到 DP。

1.3 DP 解题四步骤

这是解题的"万能框架"，考试时按这四步走：

第一步：定义状态
    → dp[i] 或 dp[i][j] 代表什么？（通常是"到第 i 个位置的最优值"）

第二步：找状态转移方程
    → dp[i] 怎么由前面的 dp 值推导出来？（这是核心！）

第三步：确定初始条件和边界
    → dp[0]、dp[1] 等于多少？

第四步：确定计算顺序
    → 从小到大？从左到右？保证计算 dp[i] 时，所依赖的值已经算好了。

二、一维 DP 经典问题

2.1 斐波那契数列（DP 视角理解）

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

DP 视角：

状态定义：dp[i] = 第 i 个斐波那契数
状态转移：dp[i] = dp[i-1] + dp[i-2]
初始条件：dp[0]=0, dp[1]=1
计算顺序：从小到大

cpp

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;
    // 可以用两个变量代替数组，优化空间
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;
}

📌 考试提示：斐波那契数列是 DP 的"入门模型"。选择题可能考"用 DP 计算 F(6) 需要多少次加法运算？"这类问题，记住：从 i=2 到 i=n，每次一次加法，共 n-1 次。

2.2 爬楼梯问题

问题：每次可以爬 1 或 2 个台阶，问爬到第 n 阶有多少种方法？

分析：

到达第 i 阶，要么从第 i-1 阶跨 1 步上来，要么从第 i-2 阶跨 2 步上来
状态转移：dp[i] = dp[i-1] + dp[i-2]
本质就是斐波那契！但初始条件不同：dp[1]=1, dp[2]=2

cpp

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    cout << climbStairs(n) << endl;
    return 0;
}

⚠️ 变式考题：如果每次可以爬 1、2 或 3 个台阶呢？状态转移变为 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。这是六级选择题的常见变形。

2.3 打家劫舍问题

问题：一排房屋，每个房屋有一定金额。相邻房屋不能同时被偷，求最大偷窃金额。

分析：

状态定义：dp[i] = 偷到第 i 个房屋时能获得的最大金额
关键决策：偷第 i 个房屋 → 不能偷第 i-1 个；不偷第 i 个 → 等于偷到第 i-1 个的最优值
状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始条件：dp[0]=nums[0], dp[1]=max(nums[0], nums[1])

cpp

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

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    if (n == 2) return max(nums[0], nums[1]);
    
    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int curr = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << rob(nums) << endl;
    return 0;
}

📌高频易错点：很多初学者会想当然地用“隔一个偷一个”的贪心策略，但这是错误的！
反例说明：假设房屋金额为 [2, 100, 3, 1, 100]。
贪心（隔一个偷）：若从第0间开始偷（偷 0, 2, 4 号），金额为 2+3+100 = 105；若从第1间开始偷（偷 1, 3 号），金额为 100+1 = 101。取最大也只有 105。
DP（正确最优解）：偷第 1 间（100）和第 4 间（100），总额为 200。
显然，贪心策略（105）远低于全局最优解（200）。打家劫舍必须用 DP 枚举“偷或不偷”的决策，不能用贪心！

2.4 数字三角形

问题：给定一个数字三角形，从顶部出发，每次可以移动到下一行相邻的左下或右下的数，求从顶到底的路径上数字之和的最大值。

分析：

状态定义：dp[i][j] = 从顶部走到第 i 行第 j 列的最大路径和
状态转移：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]（注意边界）
计算顺序：从上到下，逐行计算

cpp

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> tri(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            int x; cin >> x;
            tri[i].push_back(x);
        }
    }
    
    // 从第二行开始，自顶向下更新（每个格子 = 自身 + 上方/左上方两格的较大者）
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                tri[i][j] += tri[i-1][j];        // 最左端，只能从上方来
            } else if (j == i) {
                tri[i][j] += tri[i-1][j-1];      // 最右端，只能从左上方来
            } else {
                tri[i][j] += max(tri[i-1][j-1], tri[i-1][j]);
            }
        }
    }
    
    int ans = 0;
    for (int j = 0; j < n; j++) {
        ans = max(ans, tri[n-1][j]);
    }
    cout << ans << endl;
    return 0;
}

📌 考试提示：数字三角形是 GESP 六级的高频编程题原型。注意边界处理（每行第一个和最后一个元素的转移方向唯一）。可以自底向上计算。 自底向上写法（无需处理边界）

// 从倒数第二行开始，从下往上递推
for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        tri[i][j] += max(tri[i+1][j], tri[i+1][j+1]);
    }
}
cout << tri[0][0] << endl;  // 顶部即为答案

2.5 最大子段和

问题：给定一个整数数组，找到一个连续子数组，使得其元素之和最大，返回最大和。

分析（Kadane 算法，本质是 DP）：

状态定义：dp[i] = 以第 i 个元素结尾的最大子段和
关键决策：要么把 nums[i] 接到前面的子段后面，要么从 nums[i] 重新开始
状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])
答案：所有 dp[i] 中的最大值

cpp

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

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int dp_prev = nums[0];  // dp[0]
    int ans = dp_prev;
    for (int i = 1; i < n; i++) {
        int dp_curr = max(nums[i], dp_prev + nums[i]);
        ans = max(ans, dp_curr);
        dp_prev = dp_curr;
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << maxSubArray(nums) << endl;
    return 0;
}

⚠️ 高频易错点：状态定义中"以第 i 个元素结尾"这个限定非常关键！如果没有这个限定，就无法写出正确的状态转移方程。全为负数的情况也要能正确处理（答案就是最大的那个负数）。

三、简单背包问题

3.1 0-1 背包问题

问题描述：有 n 件物品和一个容量为 W 的背包。第 i 件物品的重量为 w[i]，价值为 v[i]。每件物品最多选一次。问：能装入背包的最大价值是多少？

核心思想

状态定义：dp[j] = 背包容量为 j 时能装的最大价值
状态转移：对于每件物品 i，枚举背包容量 j：
- 不选物品 i：dp[j] 不变
- 选物品 i：dp[j] = dp[j - w[i]] + v[i]
- 取两者的最大值：dp[j] = max(dp[j], dp[j - w[i]] + v[i])
关键：枚举顺序——外层循环枚举物品，内层循环倒序枚举容量（从 W 到 w[i]）

完整代码模板

cpp

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

int main() {
    int n, W;
    cin >> n >> W;  // n 件物品，背包容量 W
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];  // 每件物品的重量和价值
    }
    
    // dp[j] 表示容量为 j 的背包能装的最大价值
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; 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;
    return 0;
}

为什么内层要倒序遍历？

这是 0-1 背包的核心考点！

正序遍历（j 从 w[i] 到 W）：
  更新 dp[j] 时，dp[j - w[i]] 可能已经被本物品更新过了，
  相当于同一件物品被选了多次 → 变成了完全背包！

倒序遍历（j 从 W 到 w[i]）：
  更新 dp[j] 时，dp[j - w[i]] 还没有被本物品更新，
  还是"上一轮"的值 → 保证每件物品只选一次 ✓

⚠️ 这是六级选择题必考点：题目可能给出正序和倒序两种代码，问你哪个是 0-1 背包、哪个是完全背包。

空间优化原理（滚动数组）

原始二维 DP：dp[i][j] = 考虑前 i 件物品、背包容量为 j 时的最大价值。

观察状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

当前行只依赖上一行 → 可以压缩为一维数组，用倒序遍历保证正确性。空间从 O(nW) 优化到 O(W)。

3.2 完全背包问题

问题描述：与 0-1 背包相同，但每种物品可以选无限次。

与 0-1 背包的唯一区别

	0-1 背包	完全背包
物品选取	每件最多选 1 次	每件可选无限次
内层循环方向	倒序 `j = W → w[i]`	正序 `j = w[i] → W`

完全背包代码模板

cpp

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 正序遍历！允许同一物品被选多次
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    cout << dp[W] << endl;
    return 0;
}

遍历顺序差异的本质

正序遍历（完全背包）：
  dp[j] 更新时，dp[j - w[i]] 可能已经包含了物品 i
  → 物品 i 被多次选入 → 符合完全背包的定义 ✓

倒序遍历（0-1 背包）：
  dp[j] 更新时，dp[j - w[i]] 还不包含物品 i
  → 物品 i 最多被选一次 → 符合 0-1 背包的定义 ✓

📌 记忆口诀："0-1 背包倒着走，完全背包正着走"

3.3 背包问题对比总结

对比项	0-1 背包	完全背包
物品数量限制	每种 1 件	每种无限件
内层遍历顺序	倒序 `W → w[i]`	正序 `w[i] → W`
外层遍历	枚举物品	枚举物品
状态转移	`dp[j] = max(dp[j], dp[j-w[i]]+v[i])`	相同（仅遍历顺序不同）

⚠️ 高频易错点：考试中可能出现"混合背包"（有的物品只能用一次，有的可以无限用）。解法：外层遍历每件物品时，根据该物品的类型决定内层是正序还是倒序。

四、考试常见考法

选择题考法

判断 DP 适用性：给出一个问题描述，判断能否用 DP 求解（看是否满足最优子结构和重叠子问题）
读代码填空：给出不完整的 DP 代码，填写状态转移方程或遍历方向
模拟 DP 过程：给出小规模数据，手动模拟 DP 数组的变化过程
0-1 背包 vs 完全背包：给两段代码，判断哪段对应哪种背包

编程题考法

经典一维 DP：爬楼梯变式、打家劫舍变式、最大子段和
数字三角形：直接出或变形（如从底到顶、求最小路径和）
简单背包：0-1 背包或完全背包的直接应用，注意数据范围（N 和 W 通常 ≤ 1000）

五、📝 实战练习

练习题 1（单选题）

题目： 以下关于动态规划的说法，错误的是（）

A. 动态规划适用于具有最优子结构性质的问题 B. 动态规划通过保存子问题的解来避免重复计算 C. 动态规划的状态转移方程一定是 dp[i] = dp[i-1] + dp[i-2] 的形式 D. 0-1 背包问题中，一维数组实现时内层循环必须倒序遍历

🔑 点击查看答案与解析

答案： C

解析：

A 正确，最优子结构是 DP 的必要条件之一
B 正确，这是 DP 的核心思想（记忆化）
C 错误，状态转移方程因问题而异，dp[i] = dp[i-1] + dp[i-2] 只是斐波那契数列的形式。打家劫舍是 dp[i] = max(dp[i-1], dp[i-2]+nums[i])，最大子段和是 dp[i] = max(nums[i], dp[i-1]+nums[i])
D 正确，倒序保证每件物品只选一次

---

练习题 2（单选题）

题目： 有一个容量为 10 的背包，有 3 件物品，重量和价值分别为：物品 1（重量 3，价值 4）、物品 2（重量 4，价值 5）、物品 3（重量 5，价值 7）。用 0-1 背包求解，能装入背包的最大价值是（）

A. 9
B. 11
C. 12
D. 16

🔑 点击查看答案与解析

答案： C（12）

解析： 列举所有可能的组合（每件物品最多选 1 次）：

选取方案	总重量	是否 ≤ 10	总价值
物品 1	3	✓	4
物品 2	4	✓	5
物品 3	5	✓	7
物品 1+2	3+4=7	✓	4+5=9
物品 1+3	3+5=8	✓	4+7=11
物品 2+3	4+5=9	✓	5+7=12
物品 1+2+3	3+4+5=12	✗	—

最优方案为选物品 2 和物品 3，总重量 9 ≤ 10，最大价值为 12。

---

练习题 3（判断题）

题目： 动态规划的两个核心要素是"最优子结构"和"重叠子问题"。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 动态规划的两个核心要素：

最优子结构：大问题的最优解包含子问题的最优解（这是能用 DP 的前提）
重叠子问题：求解大问题时会反复用到相同子问题的解（这是 DP 比暴力高效的原因）

没有最优子结构 → 不能用 DP 没有重叠子问题 → 用 DP 没有优势（和分治一样）

💡 对比记忆：
贪心 = 最优子结构 + 贪心选择性质
DP = 最优子结构 + 重叠子问题

---

练习题 4（单选题）

题目： 爬楼梯问题：每次可以爬 1 级或 2 级台阶，爬到第 5 级台阶有多少种不同的方法？（）

A. 5
B. 8
C. 13
D. 10

🔑 点击查看答案与解析

答案： B

解析： dp[i] 表示爬到第 i 级台阶的方法数。状态转移方程：dp[i] = dp[i-1] + dp[i-2]

爬到第 i 级的最后一步：要么从 i-1 爬 1 级上来，要么从 i-2 爬 2 级上来

初始条件：

dp[1] = 1（只有 1 种：爬 1 级）
dp[2] = 2（两种：1+1 或直接 2）

计算：

dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8

选 B。

🔥 注意：这其实就是斐波那契数列！dp[i] = Fib(i+1)

---

练习题 5（单选题）

题目： 01 背包空间优化为一维数组后，内层循环（背包容量）应该怎么遍历？（）

A. 从小到大（顺序）
B. 从大到小（逆序）
C. 都可以
D. 取决于物品数量

🔑 点击查看答案与解析

答案： B

解析： 01 背包每个物品只能选一次。二维转一维时，如果 j 从小到大遍历，那么同一个物品可能被多次选中（因为后面的 dp[j] 会用到更新过的 dp[j-w]，也就是已经考虑过当前物品的状态），就变成完全背包了。

所以 01 背包必须从大到小遍历 j（逆序），这样保证 dp[j-w] 还是上一轮（没考虑当前物品）的状态，每个物品只选一次。

选 B。

🔥 必背口诀：01背包逆着走，完全背包正着走。
01背包（只能选1次）：j 从大到小（逆序）
完全背包（可重复选）：j 从小到大（顺序）

---

练习题 6（单选题）

题目： 数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子段和是？（）

A. 4
B. 5
C. 6
D. 7

🔑 点击查看答案与解析

答案： C

解析： dp[i] 表示以第 i 个元素结尾的最大子段和。状态转移：dp[i] = max(dp[i-1] + a[i], a[i]) （要么把当前元素接到前面的子段后面，要么从当前元素重新开始）

计算：

dp[0] = -2
dp[1] = max(-2+1, 1) = max(-1, 1) = 1
dp[2] = max(1+(-3), -3) = max(-2, -3) = -2
dp[3] = max(-2+4, 4) = max(2, 4) = 4
dp[4] = max(4+(-1), -1) = max(3, -1) = 3
dp[5] = max(3+2, 2) = max(5, 2) = 5
dp[6] = max(5+1, 1) = max(6, 1) = 6
dp[7] = max(6+(-5), -5) = max(1, -5) = 1
dp[8] = max(1+4, 4) = max(5, 4) = 5

dp 数组中最大值 = 6（子段 [4, -1, 2, 1]）

选 C。

💡 最大子段和也叫"最大子数组和"，是一维 DP 的经典题。结果是整个 dp 数组的最大值，不是最后一个元素！

---

练习题 7（判断题）

题目： 完全背包中，每个物品可以选无限次，空间优化后内层循环从小到大遍历。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 完全背包每个物品可以选无限次。一维数组 + 顺序遍历（j 从小到大）时，dp[j-w] 已经是更新过的（已经考虑过当前物品），这意味着当前物品可以被重复选中——正好符合完全背包的特点！

💡 对比记忆：
01 背包（1次）：逆序遍历 → 防止重复选
完全背包（无限次）：顺序遍历 → 允许重复选
记住方向，就不会搞混了！

---

练习题 8（编程题）

题目： 01 背包问题：有 n 个物品，每个物品重量 w[i]，价值 v[i]，背包容量为 W。每个物品最多选 1 次，求最大价值。

请用一维数组优化实现。

输入：第一行 n 和 W，接下来 n 行每行 w[i] 和 v[i]
输出：最大价值

样例输入：

样例输出：

（选物品2和物品3，重量4+5=9，价值5+6=11）

🔑 点击查看答案与解析

答案：

cpp

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    
    vector<int> dp(W + 1, 0);  // dp[j] = 容量j的最大价值
    
    for (int i = 0; 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;
    return 0;
}

解析： 01 背包一维优化模板：

外层循环：枚举每个物品
内层循环：从大到小枚举背包容量（逆序！）
状态转移：dp[j] = max(不选第i个, 选第i个) = max(dp[j], dp[j-w[i]] + v[i])

为什么要逆序？因为 01 背包每个物品只能选一次。逆序保证 dp[j-w[i]] 还是"上一轮"（没考虑第 i 个物品时）的状态。

时间复杂度：O(n × W) 空间复杂度：O(W)（优化前是 O(n × W)）

🔥 这是必须背下来的模板！01 背包是 DP 的入门必考题。

---

六、📊 考点总结表

考点	重要程度	出题形式	易错点
DP 两个核心要素	⭐⭐⭐⭐⭐	选择/判断	最优子结构 + 重叠子问题
DP vs 贪心	⭐⭐⭐⭐	选择/判断	贪心不回头，DP考虑所有选择
DP 解题四步骤	⭐⭐⭐⭐⭐	编程题	定状态→找转移→定初始→定顺序
爬楼梯（一维DP）	⭐⭐⭐⭐	选择/程序阅读	斐波那契变形，初始条件
最大子段和	⭐⭐⭐⭐⭐	选择/编程	结果是dp数组最大值，不是最后一个
数字三角形（二维DP）	⭐⭐⭐⭐	编程题	边界处理，转移方程
01 背包二维转移	⭐⭐⭐⭐⭐	选择/编程	dp[i][j] = max(选, 不选)
01 背包空间优化（一维逆序）	⭐⭐⭐⭐⭐	代码填空/编程	逆序！防止重复选
完全背包（一维顺序）	⭐⭐⭐⭐	选择/编程	顺序！允许重复选
01背包 vs 完全背包	⭐⭐⭐⭐⭐	选择/判断	遍历方向的区别
滚动数组优化	⭐⭐⭐	选择/代码填空	只用一行，反复利用

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       简单动态规划 · 必背速记卡             │
├─────────────────────────────────────────────┤
│  1. DP两要素：最优子结构 + 重叠子问题      │
│  2. DP四步走：定状态→找转移→定初始→定顺序 │
│  3. 贪心：勇往直前不回头；DP：三思而后行    │
│  4. 爬楼梯：dp[i] = dp[i-1] + dp[i-2]     │
│  5. 最大子段和：dp[i] = max(dp[i-1]+a[i], a[i])│
│  6. 最大子段和答案 = max(dp[i])，不是最后一个│
│  7. 01背包：每个物品最多选1次              │
│  8. 01背包二维：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)│
│  9. 01背包一维优化：j逆序（从大到小）       │
│ 10. 逆序原因：防止物品被重复选             │
│ 11. 完全背包：每个物品可选无限次           │
│ 12. 完全背包一维优化：j顺序（从小到大）     │
│ 13. 顺序原因：允许物品重复选               │
│ 14. 背包口诀：01逆着走，完全正着走         │
│ 15. DP复杂度：状态数 × 转移代价            │
└─────────────────────────────────────────────┘

第5章 简单动态规划 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、动态规划基础回顾 ​

1.1 什么是动态规划？ ​

1.2 DP 适用条件 ​

1.3 DP 解题四步骤 ​

二、一维 DP 经典问题 ​

2.1 斐波那契数列（DP 视角理解） ​

2.2 爬楼梯问题 ​

2.3 打家劫舍问题 ​

2.4 数字三角形 ​

2.5 最大子段和 ​

三、简单背包问题 ​

3.1 0-1 背包问题 ​

核心思想 ​

完整代码模板 ​

为什么内层要倒序遍历？ ​

空间优化原理（滚动数组） ​

3.2 完全背包问题 ​

与 0-1 背包的唯一区别 ​

完全背包代码模板 ​

遍历顺序差异的本质 ​

3.3 背包问题对比总结 ​

四、考试常见考法 ​

选择题考法 ​

编程题考法 ​

五、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（判断题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（编程题） ​

六、📊 考点总结表 ​

⭐ 必背速记卡 ​

第5章简单动态规划

🎯 本章学习目标

🗺️ 本章知识图谱

一、动态规划基础回顾

1.1 什么是动态规划？

1.2 DP 适用条件

1.3 DP 解题四步骤

二、一维 DP 经典问题

2.1 斐波那契数列（DP 视角理解）

2.2 爬楼梯问题

2.3 打家劫舍问题

2.4 数字三角形

2.5 最大子段和

三、简单背包问题

3.1 0-1 背包问题

核心思想

完整代码模板

为什么内层要倒序遍历？

空间优化原理（滚动数组）

3.2 完全背包问题

与 0-1 背包的唯一区别

完全背包代码模板

遍历顺序差异的本质

3.3 背包问题对比总结

四、考试常见考法

选择题考法

编程题考法

五、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（判断题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（编程题）

六、📊 考点总结表

⭐ 必背速记卡