动态规划入门：一维、背包与区间 | 王心俊老师信息学奥赛课件

情景导航

知识探究

实践应用

总结提升

分层练习作业

导航最短路

背包装物

股票交易

拼图游戏

💡 时间复杂度

💡 为什么遍历方向不同？

💡 DP的更多类型（进阶预告）

💡 学完本讲，你应该掌握的7项能力

🧩 DP两大条件

📊 一维DP

🎒 01背包

♾️ 完全背包

📐 区间DP

🔧 空间优化

用DP求最大子段和。输入 n 和 n 个整数，输出最大连续子数组的和。

🟡 B组 · 提高（4题）

01背包：n≤1000, W≤1000。输入物品重量和价值，输出最大价值。要求用一维数组优化空间。

完全背包：n种物品，每种可选无限个。背包容量W，求最大价值。

最长上升子序列（LIS）：输入 n 和 n 个整数，输出LIS长度。n ≤ 5000。

分析以下问题是否适合用DP解决，并说明理由：(1) 求数组最大值 (2) 求最短路径 (3) 求排列数

🔴 C组 · 挑战（4题）

01背包中，n=5, W=10，物品 (w,v)={(2,6),(2,3),(6,5),(5,4),(4,6)}。最大价值为（）

多重背包：n种物品，第i种最多选c[i]个。背包容量W，求最大价值。提示：转化为01背包或用二进制拆分。

最长公共子序列（LCS）：给定两个字符串 A 和 B（长度≤1000），求它们的最长公共子序列长度。

环形石子合并：n堆石子排成环形，每次合并相邻两堆，求最小代价。提示：断环成链，长度变为2n。

条件① 最优子结构

条件② 重叠子问题

核心工具：状态与转移

步骤①② 定状态 + 写转移

步骤③④ 定初值 + 定顺序

步骤⑤ 取答案

✅ 01背包（j 从大到小）

✅ 完全背包（j 从小到大）

📦 01背包：二维→一维

🔄 滚动数组

模块 01

从一个登山寻宝问题开始，感受"记住过去、避免重复"的智慧。

故事登山寻宝问题

你站在一座山的山脚下，面前有 n 个台阶通向山顶。每个台阶上都放着一些金币。

规则：你每次可以走 1 阶或 2 阶，目标是收集最多的金币。

台阶金币：[3, 2, 7, 1, 5, 8, 4, 6]

🤔 朴素想法：枚举所有可能的走法（每一步选1或2），取最大值。
但走法有 2ⁿ 种！n=40 时就有万亿种走法，根本算不完！

💡 聪明想法：站在第 i 阶时，你只需要知道"到第 i 阶最多能拿多少金币"。
而从第 i-1 阶或第 i-2 阶跨上来，取最大值即可！

dp[i] = max(dp[i-1], dp[i-2]) + coins[i]

这就是动态规划（Dynamic Programming, DP）的核心思想：记住已经算过的结果，避免重复计算！

用这个公式，只需 O(n) 时间就能算出答案。n=40 时毫秒级完成！

💡 登山寻宝手推过程

coins = [3, 2, 7, 1, 5, 8, 4, 6]（下标从1开始）

dp[1] = 3（只能走到第1阶）

dp[2] = max(dp[1], 0) + 2 = max(3, 0) + 2 = 5（从起点直接跨2阶，或走1+1）

dp[3] = max(dp[2], dp[1]) + 7 = max(5, 3) + 7 = 12

dp[4] = max(dp[3], dp[2]) + 1 = max(12, 5) + 1 = 13

dp[5] = max(dp[4], dp[3]) + 5 = max(13, 12) + 5 = 18

dp[6] = max(dp[5], dp[4]) + 8 = max(18, 13) + 8 = 26

dp[7] = max(dp[6], dp[5]) + 4 = max(26, 18) + 4 = 30

dp[8] = max(dp[7], dp[6]) + 6 = max(30, 26) + 6 = 36

答案：最多收集 36 枚金币！路径：1→2→3→4→5→6→7→8（每阶都踩，金币总和 3+2+7+1+5+8+4+6=36）

①生活类比：DP无处不在

🗺️

从A到B的最短路 = min(经过C的路, 经过D的路)。每个路口的最短路都被记住。

→ 状态记忆

🎒

容量有限，选哪些物品价值最大？逐步考虑每件物品"放/不放"。

→ 01背包DP

📊

每天决定买/卖/持有，用DP记录"第i天持有/不持有"的最大收益。

→ 状态机DP

🧩

先拼好局部小块，再逐步合并成大图。每块只需拼一次。

→ 区间DP

②DP的定义与两大条件

动态规划（Dynamic Programming）：将复杂问题分解为重叠子问题，通过记忆子问题的解来避免重复计算，从而高效求出原问题的最优解。

大问题的最优解包含小问题的最优解
如：到第i阶的最优 = max(到i-1, 到i-2) + 当前
如果子问题不独立/不最优，DP不适用

不同路径会遇到相同的子问题
如：fib(5)和fib(6)都要算fib(4)
没有重叠 → 直接分治即可

状态：dp[i] 代表什么含义
转移方程：dp[i] 如何从前面推来
这两步是DP的灵魂！

📌 本讲核心知识地图

板块	核心内容	对应大纲
DP解题五步法	定状态→写转移→定初值→定顺序→取答案	通用方法论
一维DP	最大子段和、最长上升子序列	线性DP
01背包	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)	背包DP
完全背包	每件物品可选无限次	背包DP
区间DP	dp[i][j] 表示区间[i,j]的最优解	区间DP
空间优化	滚动数组、一维压缩	优化技巧

③核心口诀

🔑 DP核心思想

记住过去，避免重复 —— 把算过的结果存起来，下次直接用！
大事化小，小事化了 —— 大问题拆成小问题，小问题逐一解决！

🔑 DP vs 贪心 vs 搜索

贪心：每步选当前最优，不回头 → 快但不一定全局最优
搜索：枚举所有可能，取最优 → 一定对但太慢
DP：记住子问题的解，避免重复 → 又快又对！
DP = 搜索 + 记忆化 = 聪明的搜索！

模块 02

掌握DP解题五步法，通过五个经典模型深入理解一维DP、背包DP和区间DP。

1DP解题五步法核心

任何DP问题都可以按以下五个步骤来解决：

状态：dp[i] 或 dp[i][j] 代表什么？
转移：dp[i] = f(dp[...])，从哪些状态推来？
这两步最难，也最关键
技巧：想"最后一步"做了什么

初值：dp[0]=? dp[1]=? 基础情况
顺序：计算dp[i]时，需要的dp[?]必须已算好
一维通常从小到大
区间DP通常从短到长

最终答案是 dp[n]？还是 max(dp[1..n])？
有时需要回溯找出具体方案
注意题目是否要求取模
验证：手算小样例！

🔑 DP通用模板

// 1. 定义状态数组
int dp[MAX]; // dp[i] = 以i结尾/到i为止的最优值

// 2. 设定初始值
dp[0] = 0; // 或 dp[1] = a[1]

// 3. 按顺序递推（转移方程）
for(int i = 1; i <= n; i++)
dp[i] = max(dp[i-1], dp[i-2]) + a[i]; // 举例

// 4. 输出答案
cout << dp[n] << endl; // 或 max(dp[1..n])

案例经典案例1：最大子段和必会

给定一个整数数组 a[1..n]，求连续子数组的最大和。例如 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 的最大子段和为 [4, -1, 2, 1] = 6。

📊 DP过程可视化：a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

a[i]

-2

-3

-1

-5

dp[i]

-2

dp[i] = max(a[i], dp[i-1] + a[i]) | 答案 = max(dp[1..n]) = 6

🔍 五步法详细分析

① 定状态：dp[i] = 以 a[i] 结尾的连续子数组的最大和（注意：必须包含 a[i]）

② 写转移：以 a[i] 结尾的子数组，要么"接上前面的"（dp[i-1]+a[i]），要么"从 a[i] 重新开始"（a[i]）

dp[i] = max(a[i], dp[i-1] + a[i])

③ 定初值：dp[1] = a[1] = -2

④ 定顺序：从左到右 i = 1, 2, ..., n

⑤ 取答案：max(dp[1], dp[2], ..., dp[n]) = 6（dp[7]对应子数组 [4,-1,2,1]）

C++max_subarray.cpp — 最大子段和

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

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

dp[1] = a[1];
    int ans = dp[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = max(a[i], dp[i-1] + a[i]);  // 转移方程
        ans = max(ans, dp[i]);              // 记录全局最大
    }

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

运行结果

输入：9
-2 1 -3 4 -1 2 1 -5 4
输出：6

案例经典案例2：最长上升子序列（LIS）必会

给定序列 a = [10, 9, 2, 5, 3, 7, 101, 18]，求最长严格递增子序列的长度。如 [2, 3, 7, 101] 长度为 4。

🔍 五步法详细分析

① 定状态：dp[i] = 以 a[i] 结尾的最长上升子序列的长度

② 写转移：对于每个 j < i，如果 a[j] < a[i]，则可以把 a[i] 接在以 a[j] 结尾的上升子序列后面

dp[i] = max(dp[j] + 1) （对所有 j < i 且 a[j] < a[i]）

如果没有满足条件的 j，则 dp[i] = 1（只有自己）

③ 定初值：所有 dp[i] = 1（每个元素自身构成长度为1的上升子序列）

④ 定顺序：i 从 1 到 n，对每个 i 枚举 j 从 1 到 i-1

⑤ 取答案：max(dp[1..n])

i	1	2	3	4	5	6	7	8
a[i]	10	9	2	5	3	7	101	18
dp[i]	1	1	1	2	2	3	4	4
转移来源	—	—	—	a[3]=2	a[3]=2	a[4]=5或a[5]=3	a[6]=7	a[6]=7

C++lis.cpp — O(n²) 解法

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

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

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

运行结果

输入：8
10 9 2 5 3 7 101 18
输出：4

上述 O(n²) 解法适用于 n ≤ 5000。当 n 更大时，可用二分优化将复杂度降至 O(n log n)。

核心思想：维护一个"上升序列"数组 d[]，每次用 lower_bound 找到替换位置。

案例经典案例3：01背包问题核心

有 n 件物品和一个容量为 W 的背包。第 i 件物品重量 w[i]，价值 v[i]。每件物品最多选一次。求能装入背包的最大价值。

🔍 五步法详细分析

① 定状态：dp[i][j] = 考虑前 i 件物品、背包容量为 j 时的最大价值

② 写转移：对于第 i 件物品，有两种选择：

• 不选第 i 件 → dp[i][j] = dp[i-1][j]

• 选第 i 件（前提是 j ≥ w[i]）→ dp[i][j] = dp[i-1][j-w[i]] + v[i]

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

③ 定初值：dp[0][j] = 0（0件物品价值为0），dp[i][0] = 0（容量为0价值为0）

④ 定顺序：i 从 1 到 n，j 从 0 到 W

⑤ 取答案：dp[n][W]

示例：n=4, W=5, 物品：(w,v) = {(2,3), (3,4), (4,5), (1,2)}

手推关键步骤：dp[4][5] = max(dp[3][5], dp[3][5-1]+2) = max(7, dp[3][4]+2) = max(7, 5+2) = 7

选中的物品：物品1(2,3) + 物品2(3,4)（重量 2+3=5，价值 3+4=7）；或物品3(4,5) + 物品4(1,2)（重量 4+1=5，价值 5+2=7）。

最终答案：dp[4][5] = 7（两种选法均为重量 5、价值 7）

C++knapsack01.cpp — 01背包（二维）

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

int dp[1005][1005];
int w[1005], v[1005];

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

for (int i = 1; i <= n; i++)
        for (int j = 0; j <= W; j++) {
            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 5
2 3
3 4
4 5
1 2
输出：7

🔑 01背包一维优化

观察转移方程 dp[i][j] 只用到 dp[i-1][...]，可以压缩为一维数组：

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 要从大到小？因为每件物品只能选一次。从小到大会导致同一件物品被重复选取（变成完全背包）！

案例经典案例4：完全背包重要

与01背包类似，但每件物品可以选无限次。

🔍 关键区别

01背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) ← 从 i-1 层转移

完全背包：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) ← 从 i 层转移（可重复选）

完全背包一维：j 从小到大遍历！

C++01背包

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

C++完全背包

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

01背包：dp[j-w[i]] 必须是"还没选第 i 件"时的值 → j 从大到小，保证 dp[j-w[i]] 还没被本轮更新过。

完全背包：dp[j-w[i]] 可以是"已经选过第 i 件"的值 → j 从小到大，dp[j-w[i]] 已被本轮更新，相当于多选了一次。

案例经典案例5：石子合并（区间DP）拓展

有 n 堆石子排成一排，每堆有 a[i] 个。每次可以合并相邻的两堆，代价为两堆石子数之和。求将所有石子合并为一堆的最小代价。

🔍 五步法详细分析

① 定状态：dp[i][j] = 合并第 i 堆到第 j 堆石子的最小代价

② 写转移：最后一次合并一定是在某个位置 k 把 [i..k] 和 [k+1..j] 两堆合在一起

dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i..j) （i ≤ k < j）

其中 sum(i..j) 是第 i 到第 j 堆的石子总数（用前缀和快速计算）

③ 定初值：dp[i][i] = 0（一堆不需要合并）

④ 定顺序：区间长度 len 从小到大（len=2,3,...,n），这是区间DP的关键！

⑤ 取答案：dp[1][n]

示例：石子 [4, 5, 9, 4]（n=4）

区间	len=1	len=2	len=3	len=4
[1,1]	0	—	—	—
[2,2]	0	—	—	—
[3,3]	0	—	—	—
[4,4]	0	—	—	—
[1,2]	—	9	—	—
[2,3]	—	14	—	—
[3,4]	—	13	—	—
[1,3]	—	—	27	—
[2,4]	—	—	31	—
[1,4]	—	—	—	40

手推过程：

len=2: dp[1][2]=4+5=9, dp[2][3]=5+9=14, dp[3][4]=9+4=13

len=3: dp[1][3]=min(dp[1][1]+dp[2][3], dp[1][2]+dp[3][3])+sum(1,3) = min(0+14, 9+0)+18 = 27

len=3: dp[2][4]=min(dp[2][2]+dp[3][4], dp[2][3]+dp[4][4])+sum(2,4) = min(0+13, 14+0)+18 = 31

len=4: dp[1][4]=min(dp[1][1]+dp[2][4], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4])+sum(1,4)

= min(0+31, 9+13, 27+0) + 22 = min(31, 22, 27) + 22 = 22 + 22 = 44

C++stone_merge.cpp — 石子合并

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

int dp[305][305], s[305], a[305];

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

memset(dp, 0x3f, sizeof(dp));  // 初始化为无穷大
    for (int i = 1; i <= n; i++) dp[i][i] = 0;

for (int len = 2; len <= n; len++)       // 区间长度从小到大
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            dp[i][j] += s[j] - s[i-1];  // 加上合并代价
        }

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

运行结果

输入：4
4 5 9 4
输出：44

⚡空间优化技巧实用

dp[i][j] 只依赖 dp[i-1][...]
压缩为一维 dp[j]
j 必须从大到小遍历
空间从 O(nW) → O(W)

dp[i] 只依赖 dp[i-1] 和 dp[i-2]
只保留2行：dp[0..1][j]
用 i%2 交替使用
空间从 O(n×m) → O(2×m)

🔑 空间优化三原则

① 先写出正确但占空间的版本
② 分析转移方程"用到了哪些旧状态"
③ 只保留必要的旧状态，注意遍历方向！

模块 03

通过详细分析的练习题，巩固DP的设计与分析能力。

题101背包手推

题目：背包容量 W=8，4件物品：(w,v) = {(3,4), (4,5), (2,3), (5,7)}。手推 dp 表并求最大价值。

提示：按五步法，逐行填写 dp[i][j] 表格。

查看参考答案

手推 dp 表：

物品\容量	2	3	4	5	6	7	8
dp[0]	0	0	0	0	0	0	0
i=1 (3,4)	0	4	4	4	4	4	4
i=2 (4,5)	0	4	5	5	5	9	9
i=3 (2,3)	3	4	5	7	8	9	9
i=4 (5,7)	3	4	5	7	8	10	11

关键步骤分析：

dp[2][7] = max(dp[1][7], dp[1][7-4]+5) = max(4, dp[1][3]+5) = max(4, 4+5) = 9（选物品1+2）

dp[3][5] = max(dp[2][5], dp[2][5-2]+3) = max(5, dp[2][3]+3) = max(5, 4+3) = 7（选物品1+3）

dp[3][8] = max(dp[2][8], dp[2][6]+3) = max(9, 5+3) = 9

dp[4][8] = max(dp[3][8], dp[3][8-5]+7) = max(9, dp[3][3]+7) = max(9, 4+7) = 11

答案：dp[4][8] = 11（选物品1(3,4)+物品4(5,7) = 重量8，价值11）

最优选法：物品1(3,4) + 物品4(5,7)，重量 3+5=8 ≤ 8，价值 4+7=11。

题2LIS详细分析

题目：序列 [3, 1, 4, 1, 5, 9, 2, 6]，求最长上升子序列的长度，并给出一个具体的LIS。

查看参考答案

逐步计算 dp[i]：

i	1	2	3	4	5	6	7	8
a[i]	3	1	4	1	5	9	2	6
dp[i]	1	1	2	1	3	4	2	4
来源	—	—	a[1]=3或a[2]=1	—	a[3]=4	a[5]=5	a[2]=1	a[5]=5或a[6]不行

详细推导过程：

dp[1]=1（只有3）

dp[2]=1（1前面没有比1小的）

dp[3]：a[1]=3<4→dp[1]+1=2; a[2]=1<4→dp[2]+1=2 → dp[3]=2（子序列{3,4}或{1,4}）

dp[4]：a[1]=3≮1; a[2]=1≮1; a[3]=4≮1 → dp[4]=1

dp[5]：a[3]=4<5→dp[3]+1=3; a[1]=3<5→dp[1]+1=2 → dp[5]=3（{3,4,5}或{1,4,5}）

dp[6]：a[5]=5<9→dp[5]+1=4 → dp[6]=4（{3,4,5,9}或{1,4,5,9}）

dp[7]：a[2]=1<2→dp[2]+1=2 → dp[7]=2（{1,2}）

dp[8]：a[5]=5<6→dp[5]+1=4; a[6]=9≮6 → dp[8]=4（{1,4,5,6}或{3,4,5,6}）

答案：LIS长度 = max(dp) = 4

具体LIS：{1, 4, 5, 9} 或 {1, 4, 5, 6} 或 {3, 4, 5, 9} 或 {3, 4, 5, 6}

题3石子合并（综合）

题目：3堆石子 [1, 2, 3]，求合并为一堆的最小代价。

查看参考答案

枚举所有合并顺序：

方案A：先合并[1,2]→代价3，得[3,3]，再合并→代价6。总代价=3+6=9

方案B：先合并[2,3]→代价5，得[1,5]，再合并→代价6。总代价=5+6=11

DP手推过程：

前缀和：s[0]=0, s[1]=1, s[2]=3, s[3]=6

dp[1][1]=0, dp[2][2]=0, dp[3][3]=0

len=2: dp[1][2]=dp[1][1]+dp[2][2]+sum(1,2)=0+0+3=3

len=2: dp[2][3]=dp[2][2]+dp[3][3]+sum(2,3)=0+0+5=5

len=3: dp[1][3]=min(dp[1][1]+dp[2][3], dp[1][2]+dp[3][3])+sum(1,3)

=min(0+5, 3+0)+6 = min(5,3)+6 = 3+6 = 9

答案：最小代价 = 9（先合并前两堆，再合并）

模块 04

1核心要点总结

知识板块	核心内容
DP两大条件	最优子结构 + 重叠子问题
解题五步法	定状态→写转移→定初值→定顺序→取答案
最大子段和	dp[i] = max(a[i], dp[i-1]+a[i])
LIS	dp[i] = max(dp[j]+1) for a[j]<a[i], O(n²)
01背包	dp[j] = max(dp[j], dp[j-w]+v)，j从大到小
完全背包	dp[j] = max(dp[j], dp[j-w]+v)，j从小到大
区间DP	dp[i][j] = min(dp[i][k]+dp[k+1][j])+cost，len从小到大
空间优化	滚动数组、一维压缩（注意遍历方向）

2拓展：DP家族全景

• 树形DP：在树上做DP，如"没有上司的舞会"（最大独立集）

• 状压DP：状态用二进制表示，如 TSP 旅行商问题

• 数位DP：按数位逐位决策，如"不含4的数字个数"

• 概率DP：求期望值，如"掷骰子到达终点的期望步数"

• 博弈DP：两人对弈，如"Nim游戏"

共同点：都是"定状态 + 写转移"，只是状态的维度和含义不同！

3思考与启发

1. 能判断一个问题是否适合用DP（最优子结构 + 重叠子问题）。

2. 能用五步法系统地解决DP问题。

3. 能写出最大子段和、LIS等一维DP的转移方程。

4. 能区分01背包和完全背包的遍历方向差异。

5. 能理解区间DP"长度从小到大"的计算顺序。

❌ 错误

LIS 问题直接输出 dp[n]，但答案应该是 max(dp[1..n])。最大子段和也有同样问题。

✅ 正确

仔细分析"答案在哪里"：背包问题 → dp[n][W]（固定位置）。LIS/子段和 → max(dp[1..n])（全局最大）。

口诀：答案位置看清楚，是dp[n]还是全局max！

速查DP模型速查表

模型	状态	转移方程	复杂度
最大子段和	dp[i]=以a[i]结尾最大和	dp[i]=max(a[i], dp[i-1]+a[i])	O(n)
LIS	dp[i]=以a[i]结尾LIS长	dp[i]=max(dp[j]+1), a[j]<a[i]	O(n²)
01背包	dp[j]=容量j最大价值	dp[j]=max(dp[j], dp[j-w]+v) 逆序	O(nW)
完全背包	dp[j]=容量j最大价值	dp[j]=max(dp[j], dp[j-w]+v) 正序	O(nW)
区间DP	dp[i][j]=区间[i,j]最优	dp[i][j]=min(dp[i][k]+dp[k+1][j])+cost	O(n³)

📌知识点笔记卡

最优子结构

重叠子问题

缺一不可

最大子段和 O(n)

LIS O(n²)

线性从左到右

每件最多选一次

j从大到小

O(nW)

每件可选无限次

j从小到大

O(nW)

dp[i][j]区间最优

len从小到大

O(n³)

滚动数组

一维压缩

注意遍历方向

课后练习

考点：逐个考察每个数作为结尾时的最长上升子序列长度，从中取最大值。

易错：把 LIS 与“相邻递增的连续段长度”混淆——子序列不要求元素在原数组中相邻。

A4编程题

查看参考答案

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n; cin >> n;
    int a[100005];
    for(int i=1;i<=n;i++) cin >> a[i];
    long long dp = a[1], ans = a[1];
    for(int i=2;i<=n;i++){
        dp = max((long long)a[i], dp + a[i]);
        ans = max(ans, dp);
    }
    cout << ans << endl;
    return 0;
}

空间优化：只用一个变量 dp 代替数组，空间 O(1)。

思路：设 dp 表示“以当前位置结尾的最大子段和”，每步在“接上前一段”和“从当前重新开始”之间取较大值。

易错：把答案写成 dp[n]（那只是以最后一个元素结尾的最优值）；或初始值全设为 0，遇到全负数数组时答错。

B1编程题

查看参考答案

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1005], w[1005], v[1005];
int main() {
    int n, W; cin >> n >> W;
    for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
    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;
    return 0;
}

关键：内层 j 从 W 到 w[i]（从大到小），保证每件物品只选一次。

思路：一维数组 dp[j] 表示容量为 j 时的最大价值，每件物品逆序枚举容量做 dp[j]=max(dp[j], dp[j-w]+v)。

易错：容量循环写成从小到大（退化成完全背包）；或 dp 数组存放上一组数据的残留值没有清零。

B2编程题

查看参考答案

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10005], w[1005], v[1005];
int main() {
    int n, W; cin >> n >> W;
    for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
    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]);
    cout << dp[W] << endl;
    return 0;
}

与01背包唯一区别：内层 j 从小到大，允许同一物品被多次选取。

思路：完全背包中物品可以无限取，把容量循环改成从小到大，同一件物品就能被反复选中。

易错：依旧使用逆序枚举容量，算法退化成 01 背包，得到的答案会比正确值小。

B3编程题

查看参考答案

#include <iostream>
#include <algorithm>
using namespace std;
int a[5005], dp[5005];
int main() {
    int n; cin >> n;
    for(int i=1;i<=n;i++){ cin >> a[i]; dp[i]=1; }
    int ans=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

思路：dp[i] 表示以 a[i] 结尾的最长上升子序列长度，用二重循环枚举前驱 j 完成转移。

易错：忘记在每轮开始时把 dp[i] 初始化为 1，或只输出 dp[n] 而没有在整个过程中维护最大值。

B4分析题

查看参考答案

(1) 求数组最大值：不适合DP。没有重叠子问题，一次遍历 O(n) 即可。虽然可以写成 dp[i]=max(dp[i-1],a[i])，但这只是递推，没有必要用DP框架。

(2) 求最短路径：适合DP（如Dijkstra本质上就是DP）。具有最优子结构（最短路上的任意一段也是最短的），且有重叠子问题。

(3) 求排列数：部分适合。如"n个元素的排列数=n!"不需要DP。但"有约束的排列数"（如某些元素不能相邻）可以用状压DP。

考点：使用 DP 的前提是同时具备“最优子结构”和“重叠子问题”，两者缺一就没必要套 DP。

易错：只要看到“能写出 dp[i]=…”就直接用 DP，忽略了没有重叠子问题时一次遍历（O(n)）就够了。

C1初赛真题

A. 15 B. 16 C. 17 D. 18

查看参考答案

答案：A. 15

选物品1(2,6)+物品5(4,6)+物品2(2,3)=重量8，价值15

选物品1(2,6) + 物品2(2,3) + 物品5(4,6)：重量 2+2+4=8 ≤ 10，价值 6+3+6 = 15（最优）

其他组合：{1,3}=重量8价值11；{1,2,3}=重量10价值14；{3,4}=重量11超重

DP 验证：dp[5][10] = 15，不存在价值更大的方案

考点：逐一枚举 5 件物品的取舍组合，在总重量不超过 10 的前提下比较总价值，取最大者。

易错：只按单位价值 v/w 从大到小贪心挑选（这是分数背包的思路），会漏掉真正的最优组合。

C2综合编程

查看参考答案

方法：二进制拆分

将第 i 种物品（最多 c[i] 个）拆成若干"组"：1, 2, 4, 8, ..., 剩余。每组当作一件独立的01背包物品。

例如 c[i]=13 → 拆成 1, 2, 4, 6（剩余=13-1-2-4=6），共4件物品。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[20005];
int main() {
    int n, W; cin >> n >> W;
    vector<pair<int,int>> items;
    for(int i=0;i<n;i++){
        int w,v,c; cin>>w>>v>>c;
        for(int k=1;k<=c;k*=2){
            items.push_back({k*w, k*v});
            c -= k;
        }
        if(c>0) items.push_back({c*w, c*v});
    }
    for(auto& p : items)
        for(int j=W;j>=p.first;j--)
            dp[j]=max(dp[j],dp[j-p.first]+p.second);
    cout << dp[W] << endl;
    return 0;
}

思路：把每种物品的数量 c[i] 按二进制拆成 1、2、4、… 若干组，每组当作一件独立的 01 背包物品处理。

易错：拆分时余数部分处理错误（13 应拆成 1、2、4、6）；或拆分后仍按容量逆序枚举，数量限制失效。

C3综合编程

查看参考答案

状态：dp[i][j] = A[1..i] 和 B[1..j] 的LCS长度

转移：如果 A[i]==B[j] → dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[1005][1005];
int main() {
    string a, b; cin >> a >> b;
    int n=a.size(), m=b.size();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[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;
}

思路：dp[i][j] 表示 A 前 i 个字符与 B 前 j 个字符的 LCS 长度，按末位字符是否相同分成两种转移。

易错：把子序列当成子串（要求字符连续），转移写错；或字符串下标从 0 开始却直接用了 dp[-1] 越界。

C4综合编程

i=1 (2,3)

i=2 (3,4)

i=3 (4,5)

i=4 (1,2)

查看参考答案

核心技巧：将环形数组复制一倍，变成长度 2n 的线性数组。然后对每个起点 i（1≤i≤n），求 dp[i][i+n-1]，取最小值。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[405][405], s[405], a[405];
int main() {
    int n; cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i]; a[i+n]=a[i]; // 断环成链
    }
    for(int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=2*n;i++) dp[i][i]=0;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=2*n;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            dp[i][j]+=s[j]-s[i-1];
        }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++) ans=min(ans,dp[i][i+n-1]);
    cout << ans << endl;
    return 0;
}

复杂度：O(n³)，n ≤ 200 时可行。关键技巧"断环成链"在很多环形DP问题中都有应用。

思路：把环形数组复制一倍变成长度 2n 的链，再按区间长度递增做区间 DP，枚举长度为 n 的各个区间取最小值。

易错：忘记把数组复制一倍就直接对原数组做区间 DP，跨越首尾的方案全部漏掉；或区间端点下标越界。

🏆洛谷原题精选（20道）

按难度排列，覆盖一维DP、背包DP、区间DP等核心考点。建议按顺序挑战！

1P1216数字三角形入门

2P1002过河卒入门

3P1020导弹拦截入门

4P1048采药入门

5P1049装箱问题入门

6P1115最大子段和入门

7P1508Likecloud-吃、吃、吃入门

8P1616疯狂的采药普及

9P1060开心的金明普及

10P1064金明的预算方案普及

11P1024一元三次方程求解普及

12P1026统计单词个数普及

13P1541乌龟棋普及

14P1052过河普及

15P1387最大正方形普及

16P1005矩阵取数游戏提高

17P1004方格取数提高

18P1373小a和uim之大逃离提高

19P1435回文字串提高

20P1880石子合并提高