动态规划

先用一句话点破 DP 的本质：

动态规划 = 把大问题拆成小问题，先解决小问题、把答案存起来，再用小问题的答案推出大问题。
它和记忆化搜索求的是同一个东西，区别只是：记忆化"自顶向下"（递归），DP"自底向上"（循环递推）。

一、从记忆化到 DP：方向的翻转（关键认知）

你在 2.4 已经用记忆化解过数字三角形了。我们对比一下，让你看清 DP 是怎么"翻转"过来的。

记忆化版本（自顶向下，递归）：

int solve(int i, int j) {        // "我要算(i,j)，需要先算它下面的"
    if (i == n-1) return a[i][j];
    if (memo[i][j] != -1) return memo[i][j];
    memo[i][j] = a[i][j] + max(solve(i+1,j), solve(i+1,j+1));
    return memo[i][j];
}

DP 版本（自底向上，循环）：

// dp[i][j] = 从(i,j)走到底的最大和
// 先算最底层，再往上推
for (int j = 0; j < n; j++) dp[n-1][j] = a[n-1][j];   // 最后一行=自己
for (int i = n-2; i >= 0; i--)                         // 从倒数第二行往上
    for (int j = 0; j <= i; j++)
        dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);  // 用下一行推
cout << dp[0][0];   // 答案在顶点

对比看清三件事：

• 记忆化是"我需要谁就去递归算谁"，DP 是"我先把需要的都算好，再算我自己"。
• 递归式 solve(i,j) = a[i][j] + max(solve(i+1,j), solve(i+1,j+1)) 和 递推式 dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]) —— 几乎一模一样！只是 solve() 变成了 dp[]，递归变成了查数组。
• DP 需要保证算 dp[i][j] 时，它依赖的 dp[i+1][...] 已经算好了——所以要从底往上循环（确定正确的递推顺序）。记忆化不用操心顺序，递归自动处理。

核心领悟：memo 数组 = dp 数组，递归式 = 递推式。 你已经会写记忆化的递归式了，那你其实已经会 DP 的递推式了——只需要把它"反过来"用循环填表。这就是为什么先学记忆化，DP 就水到渠成。

二、DP 三要素（写任何 DP 都先想这三个）

DP 的全部精髓就是这三件事。把它们想清楚，DP 题就解决了。

要素 1：状态（dp 数组表示什么）—— 最重要

dp[i]（或 dp[i][j]）到底代表哪个子问题的答案？ 这是 DP 的灵魂，状态定义对了，DP 就成功了一大半。

• 状态由几个变量决定，dp 数组就是几维。
• 状态的定义必须精确：dp[i] 是"前 i 个的答案"还是"以 i 结尾的答案"？差一个字，整道题就不同。

状态设计是 DP 最难、最需要练的部分。它和记忆化里"递归函数 solve(参数) 代表什么子问题"是完全一样的思考——你在 2.4 练的"定义状态"，就是 DP 最核心的能力。

要素 2：转移方程（状态之间怎么递推）

当前状态 dp[i] 怎么由更小的状态（dp[i-1]、dp[i-2]…）算出来？ 这就是状态转移方程，是 DP 的核心公式。

• 它回答："要得到当前问题的答案，我能基于哪些子问题的答案、怎么组合？"
• 和记忆化的递归式是同一个东西。

要素 3：初始状态（边界）与答案

• 初始状态（base case）：最小的子问题的答案，直接填（如 dp[0]=0）。对应记忆化的递归出口。
• 最终答案：在哪个 dp 值里？（是 dp[n]？还是所有 dp[i] 的 max？要想清楚。）

三、DP 的标准解题流程（套路化）

遇到一道疑似 DP 的题，按这五步走：

1. 确定状态：dp[i] 表示什么子问题（最关键，多想几种定义）。
2. 写转移方程：dp[i] 怎么由更小的状态推出。
3. 确定边界/初始值：最小子问题直接填什么。
4. 确定递推顺序：保证算 dp[i] 时它依赖的状态都算好了（通常从小到大）。
5. 找答案：最终答案是哪个 dp 值。

实战拐杖：如果第 1、2 步想不出来，先用记忆化"自顶向下"地想——"我要解决大问题，需要哪些小问题？怎么组合？" 想出递归式后，再翻译成 DP 的递推式。记忆化是你攻克 DP 的备用方案（接 2.4）。

四、能用 DP 的两个前提（识别 DP 题）

一个问题能用 DP，需要满足：

前提 1：最优子结构

大问题的最优解，可以由子问题的最优解组合得到。 比如数字三角形，从顶点的最优路径，包含了"从下一层某点出发的最优路径"。

前提 2：重叠子问题

子问题会被重复用到（否则用 DP 存起来没意义，直接递归即可）。比如斐波那契的 fib(3) 被反复计算——正是重叠子问题，才需要 DP/记忆化存结果。

怎么识别 DP 题（实用信号）：
- 求最优值（最大/最小/最长/最少）或方案数（有多少种）。
- 问题可以分解成规模更小的同类子问题。
- 当前的选择会影响后续，需要权衡（不像贪心有明显的每步最优）。
- 数据范围：DP 通常 O(n²) 或 O(n×m)，所以 n 在几百到几千、或者两个维度时，常考虑 DP（接 0.7 复杂度反推）。

看到"求最大/最小/最长/方案数" + "能拆成子问题" + "贪心好像不对"，就往 DP 想。

五、一个完整示范：最大子段和（经典入门 DP）

用这道经典题完整走一遍 DP 三要素，让你看到思维全过程。

题意：给一个数组（可能有负数），求连续子数组的最大和。

输入: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
答案: 6  （子数组 [4,-1,2,1] 的和）

第 1 步：确定状态。 关键技巧：定义 dp[i] = 以第 i 个元素结尾的最大子段和。（注意是"以 i 结尾"，这个定义让转移变得清晰——呼应 2.4 LIS 的"以 i 结尾"范式。）

第 2 步：写转移方程。 以 a[i] 结尾的最大子段和，有两种选择：

• 要么 a[i] 接在"以 a[i-1] 结尾的最大子段"后面：dp[i-1] + a[i]
• 要么 a[i] 自己重新开始一段：a[i]

取较大者：

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

（当 dp[i-1] 是负的时候，接上去只会拖累，不如自己重开。）

第 3 步：边界与答案。

• 边界：dp[0] = a[0]（第一个元素，只能它自己）。
• 答案：所有 dp[i] 的最大值（最大子段可能以任意位置结尾，不是 dp[n-1]）。

代码：

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

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]);               // 更新答案（所有结尾取max）
}
cout << ans << "\n";

复杂度 O(n)，一遍扫描。这就是完整的 DP 三要素实践。

体会一下：难点全在第 1 步状态定义——一旦确定"dp[i] = 以 i 结尾的最大子段和"，转移方程几乎是自然推出的。这印证了"状态是 DP 的灵魂"。多数 DP 题，状态想对了就成功了大半。

六、DP 的常见困难与突破

新手学 DP 的几个坎，给你心理准备和应对：

1. 想不出状态怎么定义 → 最常见的困难。突破方法：①多见经典模型（背状态定义的套路，如"以 i 结尾""前 i 个"）②先用记忆化自顶向下想 ③从"答案需要知道什么信息"反推状态。
2. 转移方程写不对 → 往往是状态没定义清楚导致的。状态精确了，转移自然清晰。
3. 边界/初始值错 → 对照记忆化的递归出口想，或手算最小情况（n=0,1）验证。
4. 答案取哪个 dp 值搞错 → 想清楚"最优解可能在哪些状态里"（是 dp[n] 还是所有 dp[i] 的最值）。

DP 能力 = 见过的模型数量 × 状态设计的熟练度。 它不像有些算法有固定模板，DP 的"模板"是一个个经典模型的状态定义套路。所以接下来的章节（线性 DP、背包、区间 DP…）本质都是在教你不同类型问题的状态怎么设计。多做题、积累状态设计的套路，是学好 DP 的唯一正道。

七、本节速记卡

• DP 本质：拆成子问题，存子问题答案，由小推大。和记忆化是一回事，方向相反（DP 自底向上循环，记忆化自顶向下递归）。
• 核心等价：dp 数组 = memo 数组，递推式 = 递归式。 会记忆化就会 DP。
• DP 三要素：①状态（dp[i] 表示什么子问题，最重要）②转移方程（怎么由小状态推出）③初始值 + 答案位置。
• 解题五步：定状态 → 写转移 → 定边界 → 定顺序 → 找答案。
• 识别信号：求最优值/方案数 + 可拆子问题 + 贪心不对。
• 状态是灵魂：状态定义对了，DP 就成功大半。想不出就先写记忆化。
• 经典范式：「以 i 结尾」「前 i 个」是两个最常用的状态定义模式。

这一节是 DP 的思维总纲。最重要的两个认知：① DP = 记忆化换方向，你不是在学全新的东西；② 状态定义是 DP 的灵魂，后面所有 DP 章节都在教你"不同问题的状态怎么设计"。

接下来的 3.2~3.5 是 DP 的具体模型——线性 DP、背包、区间 DP、树形 DP，每一个都是一类问题的状态设计套路。它们是铜牌的高频考点，也是你这两个月要重点投入的地方。有了思维总纲和记忆化基础，你会发现这些模型一个比一个顺。

下一节 3.2 线性 DP——最基础、最高频的一类 DP，包括你已经在记忆化里见过的 LIS（最长递增子序列）、LCS（最长公共子序列）、最大子段和。我们会把这些经典模型用 DP 正式过一遍，并讲透它们的状态设计套路。

配套练习题

好，给你 5 道入门 DP 题，专门练"用 DP 三要素自底向上填表"。这几道有的你在记忆化做过（数字三角形、不同路径），现在用 DP 重做，刻意对比两种写法，体会"同一道题、方向相反"。

老规矩：先自己写，重点想清楚"①状态 dp[i] 表示什么 ②转移方程 ③边界和答案位置",再展开对照。

第 1 题：最大子段和（DP 入门 —— 正文示范题）

题意：给一个数组（可能有负数），求连续子数组的最大和。

输入样例
9
-2 1 -3 4 -1 2 1 -5 4

输出样例
6

（子数组 [4,-1,2,1] 和为6）

考点：DP 三要素入门。状态 dp[i] = 以第 i 个元素结尾的最大子段和。转移 dp[i] = max(dp[i-1]+a[i], a[i])。答案是所有 dp[i] 的最大值。

#include <bits/stdc++.h>
using namespace std;

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

    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]);   // 转移：接上 or 重开
        ans = max(ans, dp[i]);               // 所有结尾取max
    }
    cout << ans << "\n";
    return 0;
}

第 2 题：爬楼梯（DP 入门 —— 斐波那契换皮）

题意：爬 n 级楼梯，每次可以爬 1 级或 2 级，问有多少种不同的爬法。

输入样例
5

输出样例
8

（5级楼梯有8种爬法）

考点：最经典的入门 DP，本质是斐波那契。状态 dp[i] = 爬到第 i 级的方法数。转移 dp[i] = dp[i-1] + dp[i-2]（最后一步爬1级从 i-1 来，或爬2级从 i-2 来）。边界 dp[1]=1, dp[2]=2。体会"方案数型 DP"的转移是相加。

提示：注意 n 大时方案数会很大，有溢出意识（这题数据小用 int 够，但要会判断）。dp[0]=1（站在地面算1种"什么都没爬"），dp[1]=1。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> dp(n + 1);
    dp[0] = 1;                       // 地面，1种"不爬"
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];   // 从i-1爬1级 或 从i-2爬2级
    cout << dp[n] << "\n";
    return 0;
}

第 3 题：数字三角形（DP 重做 —— 对比记忆化）

题意：数字三角形从顶到底，每步走下方相邻左/右，求路径和最大值。

输入样例
4
7
3 8
8 1 0
2 7 4 4

输出样例
25

考点：用 DP（自底向上） 重做 2.4 的记忆化题。状态 dp[i][j] = 从(i,j)到底的最大和。从最后一行往上递推：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])。答案在 dp[0][0]。

重点：对比你之前的记忆化写法，体会——递归式和递推式几乎一样，只是改成从底往上的循环填表。这种"对比"能让你彻底打通记忆化和DP的关系。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n), dp(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(i + 1);
        dp[i].resize(i + 1);
        for (int j = 0; j <= i; j++) cin >> a[i][j];
    }

    for (int j = 0; j < n; j++) dp[n-1][j] = a[n-1][j];   // 最后一行=自己
    for (int i = n - 2; i >= 0; i--)                       // 从倒数第二行往上
        for (int j = 0; j <= i; j++)
            dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
    cout << dp[0][0] << "\n";        // 答案在顶点
    return 0;
}

第 4 题：不同路径（DP 重做 —— 二维递推）

题意：m×n 网格，从左上 (0,0) 到右下 (m-1,n-1)，只能向右或向下，求路径数。

输入样例
3 4

输出样例
10

考点：用 DP 重做 2.4 的记忆化题。状态 dp[i][j] = 从起点到(i,j)的路径数。转移 dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上面来 + 从左边来）。边界：第一行、第一列全是1（只有一条路）。答案 dp[m-1][n-1]。

提示：① 边界——dp[0][j]=1（第一行只能一直向右）、dp[i][0]=1（第一列只能一直向下）；② 这次是从起点往终点递推（和数字三角形方向相反，但都是DP）；③ 用 long long。注意这题的状态定义和记忆化时相反（记忆化是"到终点的路径数"，这里是"从起点来的路径数"），两种都对，体会状态定义的灵活性。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<long long>> dp(m, vector<long long>(n));

    for (int j = 0; j < n; j++) dp[0][j] = 1;   // 第一行：只能向右，1条
    for (int i = 0; i < m; i++) dp[i][0] = 1;   // 第一列：只能向下，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] << "\n";
    return 0;
}

第 5 题：打家劫舍（DP —— 经典"选或不选"线性DP）

题意：一排房子，第 i 间有 a[i] 的钱。你要偷钱，但不能偷相邻的两间（会触发警报）。求能偷到的最大金额。

输入样例
5
2 7 9 3 1

输出样例
12

（偷第1、3、5间：2+9+1=12，不相邻）

考点：经典线性 DP，"选或不选"模型。状态 dp[i] = 考虑前 i 间房能偷的最大金额。转移：第 i 间偷（则 i-1 不能偷，从 dp[i-2] 来 + a[i]）或不偷（保持 dp[i-1]），取较大：dp[i] = max(dp[i-1], dp[i-2] + a[i])。这个"偷或不偷"的转移非常经典，很多题的变体都基于它。

提示：① 状态"前 i 间的最优"；② 转移核心——偷第 i 间就得跳过 i-1（用 dp[i-2]），不偷就继承 dp[i-1]；③ 边界 dp[0]=0（没房子）、dp[1]=a[1]（只有一间就偷它）；④ 注意下标处理。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

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

    dp[0] = 0;                       // 没房子
    dp[1] = a[1];                    // 只有一间，偷它
    for (int i = 2; i <= n; i++)
        dp[i] = max(dp[i-1], dp[i-2] + a[i]);  // 不偷i 或 偷i(+dp[i-2])
    cout << dp[n] << "\n";
    return 0;
}

考点回顾与它们的 DP 类型：

1. 最大子段和——"以 i 结尾" + max(接/重开)
2. 爬楼梯——方案数型（斐波那契），转移相加
3. 数字三角形——二维递推，自底向上（对比记忆化）
4. 不同路径——二维路径计数（对比记忆化）
5. 打家劫舍——"选或不选 + 隔一个"经典模型

最该吃透的认知：

• 第3、4题是关键——把它们和你的记忆化版本并排对比，你会清楚看到："递归式 = 递推式，memo = dp，自顶向下 = 自底向上"。这个对比一旦看通，DP 和记忆化在你脑子里就合二为一了。
• 第5题打家劫舍的"偷或不偷"转移是线性 DP 的经典原型——"对第 i 个元素做选择，选了就影响前一个状态"。很多线性 DP（包括后面的背包）都是这个思想的变体，务必理解。
• 方案数 DP（第2、4题）转移是相加，最优值 DP（第1、3、5题）转移是 max/min——这个区别记住。

一个重要提醒：注意每道题答案在哪个 dp 值——最大子段和是"所有 dp[i] 的max"，其他几道是"dp[n] 或 dp[终点]"。这个"答案位置"是 DP 三要素之一，容易搞错。

先框定范围：

线性 DP = 状态沿一个线性维度（数组/字符串的位置）递推的 DP。
它的状态通常是 dp[i]（一维）或 dp[i][j]（两个序列时二维），核心是把"前 i 个"或"以 i 结尾"的子问题串起来。

线性 DP 有几个必须吃透的经典模型，我逐个讲。这些是铜牌的高频考点。

一、两种核心的状态定义模式（贯穿所有线性 DP）

线性 DP 的状态定义，90% 是这两种模式之一。先把这两个刻进脑子，后面所有模型都是它们的应用：

模式 A：dp[i] = "前 i 个元素"的某个最优值/方案数。

• 特点：dp[i] 考虑了前 i 个所有元素的整体情况。
• 答案通常就是 dp[n]。
• 例子：爬楼梯、打家劫舍、背包。

模式 B：dp[i] = "以第 i 个元素结尾"的某个最优值。

• 特点：dp[i] 强制以 i 结尾，答案是所有 dp[i] 的最值。
• 例子：最大子段和、最长递增子序列（LIS）。

怎么选？ 如果"当前元素必须被使用/作为结尾"对转移有帮助，用模式 B；如果只是"考虑到第 i 个为止的整体最优"，用模式 A。这个选择是线性 DP 状态设计的核心判断，做题多了就有感觉。

二、经典模型 1：最长递增子序列（LIS）—— 必会

题意：求最长严格递增子序列的长度（子序列不要求连续）。你在 2.4 用记忆化做过，现在用 DP。

状态（模式 B）：dp[i] = 以 a[i] 结尾的最长递增子序列长度。

转移方程：枚举所有 j < i，如果 a[j] < a[i]（能接在前面），则 dp[i] = max(dp[i], dp[j] + 1)。如果前面没有更小的，dp[i] = 1（自己单独成序列）。

答案：所有 dp[i] 的最大值（LIS 可能以任意位置结尾——模式 B 的标志）。

int n;
cin >> n;
vector<int> a(n), dp(n, 1);   // dp 初始化为 1（每个数自己至少是长度1的序列）
for (int i = 0; i < n; i++) cin >> a[i];

int ans = 1;
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        if (a[j] < a[i])             // a[j] 能接在 a[i] 前
            dp[i] = max(dp[i], dp[j] + 1);
for (int i = 0; i < n; i++) ans = max(ans, dp[i]);
cout << ans << "\n";

复杂度 O(n²)。n ≤ 5000 没问题。

LIS 的"以 i 结尾"是模式 B 的典范。记住这个状态定义，类似的"最长满足某性质的子序列"都套这个。

补充：LIS 有 O(n log n) 的优化解法（用二分 + 贪心，接 1.2 的二分），n 很大时用。铜牌阶段 O(n²) 够用，O(n log n) 作为进阶了解：维护一个数组，用 lower_bound 找位置替换，能把复杂度降下来。

三、经典模型 2：最长公共子序列（LCS）—— 必会

题意：求两个字符串的最长公共子序列长度。你在 2.4 用记忆化做过。

状态（双序列）：dp[i][j] = s1 的前 i 个字符 和 s2 的前 j 个字符 的 LCS 长度。

转移方程：

• 如果 s1[i-1] == s2[j-1]（当前字符相同，注意下标，i 表示前 i 个所以字符是 i-1）：dp[i][j] = dp[i-1][j-1] + 1。
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（放弃 s1 的第 i 个，或放弃 s2 的第 j 个，取较优）。

边界：dp[0][j] = dp[i][0] = 0（任一串为空，LCS 为 0）。

答案：dp[m][n]（m、n 是两串长度）。

string s1, s2;
cin >> s1 >> s2;
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; 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[m][n] << "\n";

复杂度 O(m×n)。

LCS 是"双序列 DP"的代表——状态是"两个序列各处理到哪"，二维。这种"两个字符串/数组配对"的问题，状态几乎都是 dp[i][j] 表示"s1 前 i 个、s2 前 j 个"。编辑距离、最长公共子串等都是这个套路。双序列 DP 的状态设计范式，务必掌握。

四、经典模型 3：最大子段和 —— 已讲，归档

题意：连续子数组最大和（3.1 详细讲过）。

状态（模式 B）：dp[i] = 以 a[i] 结尾的最大子段和。 转移：dp[i] = max(dp[i-1] + a[i], a[i])。 答案：所有 dp[i] 的最大值。

这是模式 B 的另一个典范。注意 LIS 和最大子段和都是"以 i 结尾"，但一个求最长、一个求最大和——同样的状态模式，适配不同的目标。

五、经典模型 4：编辑距离（双序列 DP 进阶，了解）

题意：把字符串 s1 变成 s2，每次可以插入、删除、替换一个字符，求最少操作次数。

状态：dp[i][j] = 把 s1 前 i 个字符变成 s2 前 j 个字符的最少操作数。

转移方程：

• 如果 s1[i-1] == s2[j-1]（当前字符相同，不用操作）：dp[i][j] = dp[i-1][j-1]。
• 否则取三种操作的最小 + 1：

dp[i][j] = 1 + min({
    dp[i-1][j],    // 删除 s1 的第 i 个字符
    dp[i][j-1],    // 在 s1 插入一个字符（匹配 s2 的第 j 个）
    dp[i-1][j-1]   // 替换 s1 的第 i 个为 s2 的第 j 个
});

边界：dp[i][0] = i（s2 空，要删光 s1 的 i 个字符）、dp[0][j] = j（s1 空，要插入 j 个字符）。

答案：dp[m][n]。

编辑距离是 LCS 的"亲戚"，同样是双序列 DP，但转移考虑三种操作。铜牌阶段了解，理解"三种操作对应三个子状态"即可。它在实际应用（拼写检查、DNA 比对）中很重要。

六、线性 DP 的更多变体（拓宽视野）

线性 DP 还有很多变体，核心都是"在一维上递推 + 对每个元素做某种决策"：

• 打家劫舍系列（3.1 讲过）：选或不选 + 不能相邻。变体有"环形房子""树形房子（树形 DP）"。
• 跳跃游戏：dp[i] = 能否到达第 i 格 / 到第 i 格的最少跳数。
• 解码方法：一串数字有多少种解码方式（类似爬楼梯的方案数 DP，但带约束）。
• 最长递增子序列的变体：最长不下降、最长连续递增、二维 LIS（导弹拦截、合唱队形等经典题）。

这些变体的共性：状态是 dp[i]（前 i 个或以 i 结尾），转移是对第 i 个元素做某种选择/判断。见多了就能快速套用。

七、线性 DP 解题思维（套路化）

遇到疑似线性 DP 的题：

1. 判断是单序列还是双序列：一个数组/字符串 → 一维 dp[i]；两个 → 二维 dp[i][j]。
2. 选状态模式：「前 i 个」（模式 A）还是「以 i 结尾」（模式 B）？
3. 对第 i 个元素，想"决策"：用它/不用它？接在谁后面？和另一个序列的第 j 个匹配吗？这就引出转移。
4. 写转移方程 + 边界。
5. 确定答案位置：模式 A 通常 dp[n]，模式 B 通常所有 dp[i] 的最值。

八、本节速记卡

• 线性 DP：状态沿一维（数组/字符串位置）递推。
• 两种核心状态模式：
• 模式 A「前 i 个」→ 答案 dp[n]（爬楼梯、打家劫舍）
• 模式 B「以 i 结尾」→ 答案所有 dp[i] 的最值（最大子段和、LIS）
• 四大经典模型：
• LIS（最长递增子序列）：dp[i]=以i结尾的长度，枚举前驱，O(n²)。
• LCS（最长公共子序列）：dp[i][j]=两串前i、前j的LCS，双序列。
• 最大子段和：dp[i]=以i结尾，max(接/重开)。
• 编辑距离：dp[i][j]，三种操作取min。
• 双序列 DP：两个序列配对 → dp[i][j] 表示"各处理到哪"（LCS、编辑距离）。
• 思维：单/双序列 → 选状态模式 → 对第i个做决策 → 转移。

线性 DP 是 DP 的基本功。它的两种状态模式（"前 i 个" vs "以 i 结尾"）和双序列的 dp[i][j] 范式，是后面所有 DP 的基础。LIS 和 LCS 这两个模型尤其重要——它们是无数变体的原型，几乎每场比赛都可能遇到它们的影子，务必把状态定义和转移背到滚瓜烂熟。

下一节 3.3 背包——DP 里最经典、最重要的一类模型（01 背包、完全背包、多重背包）。背包问题有极其固定的模板和"套路"，是铜牌的必考点，学好了能稳定拿分。它本质也是线性 DP（对每个物品做"选或不选"的决策，呼应打家劫舍的思想），但因为太重要、套路太鲜明，单独成节。

配套练习题

好，给你 6 道线性 DP 题，覆盖两大状态模式和四个经典模型的变体。重点练"选状态模式（前 i 个 vs 以 i 结尾）+ 写转移方程"。这些模型是 DP 思维的核心训练。

老规矩：先自己写，重点想清楚"状态怎么定义、转移方程、答案在哪",再展开对照。

第 1 题：最长递增子序列（LIS —— 必会模型）

题意：求最长严格递增子序列的长度。

输入样例
7
1 7 3 5 9 4 8

输出样例
4

（如 1 3 5 9 或 1 3 5 8 或 1 3 4 8，长度4）

考点：模式 B（以 i 结尾）。dp[i] = 以 a[i] 结尾的 LIS 长度，枚举前驱 j（a[j]<a[i]）取 dp[j]+1 最大。答案是所有 dp[i] 的最大值。

#include <bits/stdc++.h>
using namespace std;

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

    int ans = 1;
    for (int i = 0; i < n; i++) {
        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 << "\n";
    return 0;
}

第 2 题：最长公共子序列（LCS —— 必会模型）

题意：求两个字符串的最长公共子序列长度。

输入样例
abcbdab
bdcaba

输出样例
4

（如 bdab 或 bcba，长度4）

考点：双序列 DP。dp[i][j] = s1前i个、s2前j个的LCS。字符相同 dp[i-1][j-1]+1，不同 max(dp[i-1][j], dp[i][j-1])。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; 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[m][n] << "\n";
    return 0;
}

第 3 题：最长连续递增序列（LIS 变体 —— 练"连续"约束）

题意：求最长连续递增子序列的长度（这次要求连续，即在原数组中位置也连续）。

输入样例
6
1 3 5 4 7 8

输出样例
3

（连续递增的 4 7 8，或 1 3 5，长度3。注意 1 3 5 7 8 不连续，因为中间隔了个4）

考点：LIS 的变体，但因为要求连续，转移简单很多——dp[i] = 以 a[i] 结尾的最长连续递增长度，只需看前一个 a[i-1]：如果 a[i] > a[i-1] 则 dp[i]=dp[i-1]+1，否则 dp[i]=1。对比第1题：不连续的LIS要枚举所有前驱O(n²)，连续的只看前一个O(n)。 体会"连续"约束如何简化转移。

提示：只依赖 dp[i-1]，O(n) 解决。答案是所有 dp[i] 的最大值。

#include <bits/stdc++.h>
using namespace std;

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

    int ans = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i-1]) dp[i] = dp[i-1] + 1;  // 只看前一个！
        else dp[i] = 1;                           // 断了，重新开始
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}

第 4 题：打家劫舍 II（环形 —— 经典变体）

题意：和打家劫舍一样（不能偷相邻的），但这次房子排成一个环（第 1 间和第 n 间也相邻）。求最大金额。

输入样例
4
2 3 2 1

输出样例
4

（环形，第1和第4相邻。偷第2、4不行（相邻）。偷第1、3：2+2=4；或偷第2：3。最优是偷1和3得4... 等等第1和第3不相邻，2+2=4✓）

考点：环形 DP 的经典处理技巧——拆成两种情况各做一次普通打家劫舍：① 偷第1间（则第n间不能偷）→ 对房子 [1, n-1] 做普通打家劫舍；② 不偷第1间 → 对房子 [2, n] 做普通打家劫舍。两者取最大。这个"环形拆成两段线性"的技巧很重要。

提示：写一个普通打家劫舍函数 rob(l, r) 处理区间 [l,r]，然后 max(rob(1, n-1), rob(2, n))。注意 n=1 的特判。

#include <bits/stdc++.h>
using namespace std;

vector<int> a;

int rob(int l, int r) {          // 对区间[l,r]做普通打家劫舍
    if (l > r) return 0;
    int prev2 = 0, prev1 = 0;    // dp[i-2], dp[i-1]（滚动变量）
    for (int i = l; i <= r; i++) {
        int cur = max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) { cout << a[1] << "\n"; return 0; }  // 特判
    // 环形拆两种：偷1(不能偷n)→[1,n-1]；不偷1→[2,n]
    cout << max(rob(1, n-1), rob(2, n)) << "\n";
    return 0;
}

第 5 题：解码方法（计数型线性DP —— 带约束，有难度）

题意：一条只含数字的字符串，按 1→A, 2→B, ..., 26→Z 解码。比如 "12" 可以解码成 "AB"(1,2) 或 "L"(12)。给一个数字串，求有多少种解码方法。（注意：0 不能单独解码，且 "06" 这种前导0的两位数也不合法）

输入样例
226

输出样例
3

（"226" 可解码为 "BBF"(2,2,6)、"BZ"(2,26)、"VF"(22,6)，共3种）

考点：方案数型线性 DP（类似爬楼梯但带约束）。dp[i] = 前 i 个字符的解码方法数。转移：① 如果第 i 个数字非0，可单独解码，dp[i] += dp[i-1]；② 如果第 i-1、i 两位组成的数在 10~26 之间，可两位一起解码，dp[i] += dp[i-2]。练习"带约束的方案数DP"——转移时要判断合法性。

提示：① dp[0]=1（空串1种）；② 单个字符：s[i-1] != '0' 时 dp[i] += dp[i-1]；③ 两个字符：s[i-2]s[i-1] 组成的数在 [10,26] 时 dp[i] += dp[i-2]；④ 注意 '0' 的处理（"10"合法但"0"和"06"不行）。这题坑较多，仔细处理边界。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;                       // 空串1种
    dp[1] = (s[0] != '0') ? 1 : 0;   // 第一个字符（非0才能解码）

    for (int i = 2; i <= n; i++) {
        // 单独解码第i个字符（非0）
        if (s[i-1] != '0') dp[i] += dp[i-1];
        // 两位一起解码（s[i-2]s[i-1] 在10~26）
        int two = (s[i-2] - '0') * 10 + (s[i-1] - '0');
        if (two >= 10 && two <= 26) dp[i] += dp[i-2];
    }
    cout << dp[n] << "\n";
    return 0;
}

第 6 题：导弹拦截（LIS 应用 —— 经典综合，有难度）

题意：一套拦截系统，每发炮弹不能高于前一发的高度（即拦截的高度序列必须单调不增）。给出依次飞来的导弹高度，求这套系统最多能拦截多少导弹。

输入样例
8
389 207 155 300 299 170 158 65

输出样例
6

（最多拦截6枚：389 300 299 170 158 65，是一个不增子序列）

考点：LIS 的变形——求最长不增子序列的长度。和标准 LIS 的区别只是比较方向：标准 LIS 求最长递增，这里求最长不增（≥）。dp[i] = 以第 i 枚结尾能拦截的最多导弹数，枚举前驱 j（a[j] >= a[i]）取 dp[j]+1。体会 LIS 模型的灵活变形——改变比较符号就能解决不同的"最长子序列"问题。

提示：和第1题几乎一样，只把 a[j] < a[i] 改成 a[j] >= a[i]（前一发要 ≥ 当前，才能接上形成不增序列）。答案是所有 dp[i] 的最大值。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

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

    int ans = 1;
    for (int i = 0; i < n; i++) {
        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 << "\n";
    return 0;
}

考点回顾：

1. LIS——模式B经典，枚举前驱
2. LCS——双序列DP
3. 最长连续递增——LIS变体（连续约束简化转移）
4. 打家劫舍II——环形拆两段（破环为链）
5. 解码方法——方案数DP（带合法性约束）
6. 导弹拦截——LIS变形（改比较符号）

最该吃透的认知：

• 第1、3、6题串起来看——都是"最长子序列"问题，但：标准LIS要枚举前驱(O(n²))，连续LIS只看前一个(O(n))，导弹拦截改个符号求不增。同一个模型，约束不同、目标不同，转移随之变化。这种"举一反三"是 DP 的核心能力。
• 第4题的"破环为链"——环形问题拆成两个线性问题各做一次，是处理环形DP的通用套路。
• 方案数DP（第5题）转移相加 + 带合法性判断——很多计数DP都要在转移时检查约束（这位能不能解码、这步合不合法）。

一个重要观察：你应该感觉到，线性DP的题目千变万化，但状态定义就那两种模式（前i个 / 以i结尾），转移就是"对第i个元素做决策"。掌握了这个框架 + 几个经典模型，大部分线性DP都能套。

先建立全局认识：

背包问题 = 有一个容量有限的背包和若干物品，每个物品有"体积"和"价值"，选一些物品装进背包，在不超容量的前提下让总价值最大。
核心是对每个物品做"选还是不选"（以及"选几个"）的决策，用 DP 求最优。

背包有三种基本类型，我按重要性讲：01 背包（最重要）→ 完全背包 → 多重背包。

一、01 背包（最核心，必须烂熟）

问题描述

有 n 件物品和容量为 W 的背包。第 i 件物品体积 v[i]、价值 w[i]。每件物品只有一件（要么选，要么不选，所以叫"01"）。求背包能装的最大价值。

例：容量 W=10，物品：
  物品1: 体积2, 价值3
  物品2: 体积3, 价值4
  物品3: 体积4, 价值5
  物品4: 体积5, 价值6
最优：选物品2+3+... 让总价值最大

二维 DP（先理解这个，再优化）

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

转移方程（核心——对第 i 件物品"选或不选"）：

• 不选第 i 件：dp[i][j] = dp[i-1][j]（容量没用，价值不变，继承前 i-1 件的结果）。
• 选第 i 件（前提 j >= v[i]，装得下）：dp[i][j] = dp[i-1][j-v[i]] + w[i]（腾出 v[i] 的空间装它，价值加 w[i]）。
• 取两者较大：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])    // 当 j >= v[i]
dp[i][j] = dp[i-1][j]                                  // 当 j < v[i]，装不下只能不选

边界：dp[0][j] = 0（没物品，价值 0）。 答案：dp[n][W]。

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

vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];                    // 不选第 i 件
        if (j >= v[i])                            // 装得下才考虑选
            dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);  // 选第 i 件
    }
cout << dp[n][W] << "\n";

这个"选或不选"的转移是背包的灵魂，和打家劫舍的"偷或不偷"同源。理解它：每件物品独立决策，选了就从"少了它体积的子问题"转移过来 + 它的价值。

一维滚动优化（必须掌握，实战都用这个）

观察到 dp[i][...] 只依赖 dp[i-1][...]（上一行），所以可以用一维数组滚动，把空间从 O(nW) 降到 O(W)。

优化后：

vector<int> dp(W+1, 0);
for (int i = 1; i <= n; i++)
    for (int j = W; j >= v[i]; j--)      // 注意：j 从大到小！
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
cout << dp[W] << "\n";

最关键的点——`j 必须从大到小遍历（这是 01 背包的标志性细节，极易错）：

• 为什么从大到小：一维数组里，dp[j] 更新时要用 dp[j-v[i]]，而这个值必须是"上一轮（前 i-1 件）"的旧值（保证每件物品只用一次）。从大到小遍历，更新 dp[j] 时 dp[j-v[i]]（下标更小）还没被本轮更新过，仍是旧值——保证了"01"（每件只选一次）。
• 如果从小到大，dp[j-v[i]] 会先被本轮更新（变成"选了第 i 件后的值"），再用它更新 dp[j]，相当于第 i 件被选了多次——那就变成完全背包了（见下文）。

01 背包一维模板（背死）：

solution.cpp

for (int i = 1; i <= n; i++)
    for (int j = W; j >= v[i]; j--)        // 倒序！
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

"01 背包，容量倒序" 这句口诀刻进脑子。

二、完全背包（每件物品无限个）

问题描述

和 01 背包一样，但每件物品有无限件（可以选任意多个）。求最大价值。

转移与 01 的唯一区别：遍历方向

状态相同：dp[j] = 容量 j 时的最大价值。 转移相同：dp[j] = max(dp[j], dp[j-v[i]] + w[i])。 唯一区别：`j 从小到大遍历！

vector<int> dp(W+1, 0);
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= W; j++)      // 注意：j 从小到大！
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
cout << dp[W] << "\n";

为什么从小到大：正如上面分析的，从小到大时 dp[j-v[i]] 已经被本轮更新（可能已经选了第 i 件），再用它更新 dp[j]，就允许第 i 件被重复选取——这正是完全背包"无限个"的要求。

01 背包 vs 完全背包，代码只差遍历方向：
- 01 背包：for (j = W; j >= v[i]; j--) 倒序（每件一次）。
- 完全背包：for (j = v[i]; j <= W; j++) 正序（每件无限次）。

记忆："01 倒序，完全正序"。这是背包最精妙也最容易混的地方，务必分清。理解了"倒序保证旧值（用一次）、正序用新值（用多次）"，就不会错。

联系 2.4：还记得那道"硬币凑数最少硬币"吗？那就是完全背包（每种硬币无限个）！凑硬币、完全背包是一回事。

三、多重背包（每件物品有限个）

问题描述

每件物品有 c[i] 个（限定数量，介于 01 和完全之间）。求最大价值。

最朴素解法：拆成 01 背包

把"第 i 件有 c[i] 个"拆成 c[i] 件相同的物品，然后跑 01 背包：

// 把每件物品按数量拆开，当成多个独立物品做 01 背包
for (int i = 1; i <= n; i++)
    for (int k = 0; k < c[i]; k++)        // 拆成 c[i] 个
        for (int j = W; j >= v[i]; j--)   // 01 背包（倒序）
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

复杂度：O(W × 总物品数)。如果数量不大，这个朴素拆分够用。

二进制优化（进阶，了解）：当 c[i] 很大时，朴素拆分会超时。可以用"二进制拆分"——把 c[i] 个物品拆成 1,2,4,8...个的"打包物品"（log 个），用更少的物品表示所有可能的选取数量，把复杂度降到 O(W × Σlog(c[i]))。铜牌阶段如果遇到数量大的多重背包再学，朴素拆分能应付大部分题。

四、背包问题的常见变体（识别与套用）

背包的"皮"很多，但内核就是那个转移。常见变体：

变体 1：恰好装满

要求恰好装满背包（而非"不超过"）。区别在初始化：

• 求"不超过容量的最大价值"：dp 全初始化为 0（任何容量下"什么都不装"价值0，合法）。
• 求"恰好装满的最大价值"：dp[0]=0，其余 dp[j]=-∞（表示"容量 j 恰好装满"初始不可达，只有从合法状态转移来才有效）。

// 恰好装满的初始化
vector<int> dp(W+1, -1e9);   // 负无穷表示不可达
dp[0] = 0;                    // 容量0恰好装满=价值0
// ... 转移相同 ...
cout << (dp[W] < 0 ? "无解" : to_string(dp[W])) << "\n";

"恰好装满"看初始化：这个区别很经典，务必记住——普通背包全0初始化，恰好装满只有 dp[0]=0、其余-∞。

变体 2：求方案数（而非最大价值）

把"求最大价值"改成"有多少种装法"。转移从 max 变成求和：

// 完全背包求方案数（如：用硬币凑出金额的方案数）
dp[0] = 1;                    // 凑出0元有1种方法（什么都不选）
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= W; j++)
        dp[j] += dp[j-v[i]];  // 累加方案数（不是max！）

方案数背包转移用加法（呼应 3.1 "方案数 DP 转移相加"）。"凑硬币有多少种方案"就是这个。

变体 3：二维费用背包

物品有两种限制（比如既限重量又限体积）。状态多一维：dp[j][k]（容量 j、另一限制 k）。转移类似，多一层循环。铜牌阶段了解。

变体 4：01 背包判定可行性

"能否选出物品恰好凑成某个值"（接 2.3 子集和、3.1 分割等和子集）。dp[j] 是 bool，dp[j] = dp[j] || dp[j-v[i]]。

分割等和子集（2.3 做过的搜索题）其实就是 01 背包判定——容量是 sum/2，看能否恰好装满。很多搜索题用背包 DP 做更快！

五、背包问题识别信号

看到这些特征，想到背包：

• "从 n 个物品里选一些，受某个容量/总量限制，求最大价值/最多数量/方案数" → 背包。
• 关键词："容量""体积""重量""预算"等限制 + "价值""数量"最大 或 "方案数"。
• 判断哪种背包：每个物品选一次 → 01；无限次 → 完全；有限次 → 多重。
• 数据范围：物品数 n 和容量 W 都不太大（n、W 在几千以内），O(nW) 能过 → 背包。

六、背包问题解题流程

1. 识别是背包：选物品 + 容量限制 + 求最值/方案数。
2. 判断类型：01（每个一次）/ 完全（无限）/ 多重（有限）。
3. 定义状态：dp[j] = 容量 j 时的最优值/方案数（一维滚动）。
4. 写转移 + 选对遍历方向：01 倒序，完全正序。
5. 处理变体：恰好装满（改初始化）、方案数（max 改加法）、判定（改 bool）。
6. 答案：dp[W]。

七、本节速记卡

• 背包本质：容量限制下选物品求最值，核心是"对每个物品选或不选"的 DP。
• 01 背包（每件一次）：一维 dp[j]，转移 dp[j]=max(dp[j], dp[j-v[i]]+w[i])，容量倒序 j: W→v[i]。最重要，必背。
• 完全背包（无限件）：转移相同，容量正序 j: v[i]→W。
• 口诀："01 倒序，完全正序"（倒序用旧值=选一次，正序用新值=选多次）。
• 多重背包（有限件）：拆成 01 背包（数量大用二进制优化）。
• 变体：
• 恰好装满：dp[0]=0，其余 -∞。
• 方案数：max 改加法，dp[0]=1。
• 可行性判定：dp 改 bool，用 ||。
• 识别：选物品 + 容量限制 + 求最值/方案数。

背包是 DP 里"模板最固定、最容易拿分"的部分。它不像 LIS/LCS 那样要灵活设计状态——背包的状态和转移高度套路化，你需要做的是把那个一维模板背熟，分清 01 和完全的遍历方向，认识各种变体。这是铜牌阶段性价比极高的得分点。

最关键的两件事：① "01 倒序，完全正序" 这个遍历方向的区别，是背包的命门，务必理解透（理解了"旧值用一次、新值用多次"就永远不会错）；② 认识背包的各种"皮"——很多题不直接说"背包"，但本质是背包（凑硬币、分割等和子集、方案数统计），能识别出来就能套模板。

下一节 3.4 区间 DP——另一类重要的 DP 模型，状态是"一个区间 [l,r]"，通过合并小区间得到大区间的解。它是铜牌会涉及的模型（石子合并是经典题），思维上比背包更需要"从小区间往大区间推"的转变。

配套练习题

好，给你 6 道背包题，覆盖 01/完全/恰好装满/方案数/可行性判定，外加"披着外衣的背包"。背包是稳定拿分点，把模板和遍历方向练到肌肉记忆很值。

老规矩：先自己写，重点想清楚"哪种背包、遍历方向（倒序还是正序）、初始化怎么设",再展开对照。

第 1 题：01 背包（模板裸题 —— 必背）

题意：n 件物品，背包容量 W。第 i 件体积 v[i]、价值 w[i]，每件只能选一次。求最大价值。

输入样例
4 10
2 3
3 4
4 5
5 6

输出样例
13

（选物品2(3,4)+3(4,5)+... 体积3+4+? 选2,3,4：体积3+4+5=12>10。选1,2,3：2+3+4=9≤10，价值3+4+5=12。选1,2,4：2+3+5=10，价值3+4+6=13✓）

考点：01 背包一维模板。dp[j]=max(dp[j], dp[j-v[i]]+w[i])，容量倒序。这是必须背死的模板。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = W; j >= v; j--)          // 倒序！每件只选一次
            dp[j] = max(dp[j], dp[j-v] + w);
    }
    cout << dp[W] << "\n";
    return 0;
}

第 2 题：完全背包（模板裸题）

题意：同上，但每件物品有无限个。求最大价值。

输入样例
4 10
2 3
3 4
4 5
5 6

输出样例
15

（物品1(2,3)选5个：体积10，价值15。这是最优）

考点：完全背包。和 01 唯一区别——容量正序。对比第1题（同样输入），体会"倒序vs正序"导致的不同结果（01选一次得13，完全可重复选得15）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= W; j++)          // 正序！每件可选多次
            dp[j] = max(dp[j], dp[j-v] + w);
    }
    cout << dp[W] << "\n";
    return 0;
}

第 3 题：恰好装满（变体 —— 练初始化）

题意：n 件物品（每件一次，01 背包），背包容量 W。求恰好装满背包时的最大价值，如果无法恰好装满输出 -1。

输入样例
3 10
3 4
5 6
6 7

输出样例
13

（恰好装满10：选3+... 3+? 凑10。选物品1(3)+? 没有7。选物品2(5)+? 没有5。选物品1(3)+物品... 3+6=9≠10。其实选不出恰好10？让我重算：体积3,5,6，凑10：5+... 没有5；3+... 3+6=9，3+5=8；单个都不行。两两：3+5=8,3+6=9,5+6=11；三个3+5+6=14。确实凑不出10，应输出-1。样例数据我调整）

修正样例：

输入
3 8
3 4
5 6
6 7

输出
10

（恰好装满8：物品1(3)+物品2(5)=体积8✓，价值4+6=10）

考点：恰好装满的初始化技巧。dp[0]=0，其余 dp[j]=-∞（表示不可达）。最后 dp[W]<0 说明无法装满，输出-1。练习"恰好装满看初始化"。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, -1e9);   // 关键：其余设为负无穷（不可达）
    dp[0] = 0;                      // 容量0恰好装满=价值0
    for (int i = 0; i < n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = W; j >= v; j--)
            dp[j] = max(dp[j], dp[j-v] + w);
    }
    cout << (dp[W] < 0 ? -1 : dp[W]) << "\n";
    return 0;
}

第 4 题：凑硬币方案数（方案数背包 —— 重要）

题意：有几种面值的硬币（每种无限个），求凑出金额 amount 的方案数（不同的硬币组合算不同方案，但顺序不算，即 1+2 和 2+1 是同一种）。

输入样例
3 5
1 2 5

输出样例
4

（凑5的方案：1+1+1+1+1、1+1+1+2、1+2+2、5，共4种）

考点：方案数型完全背包。dp[j] = 凑出金额 j 的方案数。转移 dp[j] += dp[j-coin]（加法，不是max）。初始化 dp[0]=1。完全背包正序遍历。练习"方案数背包用加法"。

提示：① dp[0]=1（凑0元有1种：什么都不选）；② 外层枚举硬币、内层正序枚举金额；③ dp[j] += dp[j-coin]。注意循环顺序：外层硬币、内层金额，这样保证组合不重复（1+2和2+1算一种）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, amount;
    cin >> n >> amount;
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;                      // 凑0元1种方法
    for (int i = 0; i < n; i++) {
        int coin;
        cin >> coin;
        for (int j = coin; j <= amount; j++)   // 完全背包，正序
            dp[j] += dp[j-coin];    // 方案数累加（不是max！）
    }
    cout << dp[amount] << "\n";
    return 0;
}

第 5 题：分割等和子集（披着外衣的背包 —— 重要识别）

题意：给一个正整数数组，判断能否分成两个和相等的子集。能输出 YES，否则 NO。

输入样例
4
1 5 11 5

输出样例
YES

（{1,5,5} 和 {11}，都是11）

考点：这其实是 01 背包判定问题（你在 2.3 用搜索做过，现在用背包 DP，更快）！转化：能否选出若干数恰好凑成 sum/2。dp[j] = bool，表示能否凑出和 j。转移 dp[j] = dp[j] || dp[j-a[i]]。练习"识别出这是背包"+ 可行性判定背包。

提示：① 求总和，奇数直接NO；② target=sum/2，做01背包判定；③ dp[j] 是bool，dp[0]=true，转移 dp[j] = dp[j] || dp[j-a[i]]（倒序，因为是01）；④ 最后看 dp[target]。这题让你体会：很多"能否凑出""能否分割"的题，本质都是背包判定。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
    if (sum % 2 != 0) { cout << "NO\n"; return 0; }   // 奇数无法平分

    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;                   // 凑出0总是可以（不选）
    for (int i = 0; i < n; i++)
        for (int j = target; j >= a[i]; j--)   // 01背包，倒序
            dp[j] = dp[j] || dp[j-a[i]];        // 能否凑出j
    cout << (dp[target] ? "YES" : "NO") << "\n";
    return 0;
}

第 6 题：目标和（背包变体 —— 有难度，思维转化）

题意：给一个非负整数数组和一个目标值 target。给每个数前面添加 + 或 -，使表达式结果等于 target。求有多少种添加符号的方法。

输入样例
5 3
1 1 1 1 1

输出样例
5

（5个1，要凑出3：需要4个+1个-（+1+1+1+1-1=3），共C(5,1)=5种选哪个数为负的方法）

考点：巧妙转化成背包。设选 + 的数之和为 P，选 - 的之和为 N，则 P - N = target 且 P + N = sum（总和）。解得 P = (target + sum) / 2。于是问题变成：从数组中选若干数，使和恰好为 P，求方案数——这就是 01 背包方案数！练习"把看似不相关的问题转化成背包"。

提示：① 推导 P = (target+sum)/2；② 若 target+sum 为奇数或 P<0，无解（输出0）；③ 转成"01背包：选数凑和为P的方案数"，dp[j] += dp[j-a[i]]（倒序，01背包，方案数用加法）；④ dp[0]=1。这题的精髓是数学转化，把"加减符号"问题变成"选子集凑目标和"。想不出可看答案。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }

    // 推导：选+的和为P，P = (target + sum) / 2
    if ((target + sum) % 2 != 0 || target + sum < 0) { cout << 0 << "\n"; return 0; }
    int P = (target + sum) / 2;

    vector<long long> dp(P + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = P; j >= a[i]; j--)   // 01背包方案数，倒序
            dp[j] += dp[j-a[i]];
    cout << dp[P] << "\n";
    return 0;
}

考点回顾：

1. 01 背包——倒序模板（必背）
2. 完全背包——正序模板
3. 恰好装满——初始化 -∞
4. 凑硬币方案数——加法转移
5. 分割等和子集——01背包判定（识别外衣）
6. 目标和——数学转化成背包

最该吃透的认知：

• 第1、2题对比——同样输入，倒序（01）得13、正序（完全）得15。"01倒序、完全正序"是背包的命门，理解"倒序用旧值=选一次、正序用新值=选多次"，永远不会混。
• 第5、6题的"识别与转化"——很多题不说"背包"，但本质是背包：分割等和子集是"凑sum/2的判定"，目标和是"凑P的方案数"。能把陌生问题转化成背包模型，是背包真正的价值，比会背模板更重要。
• 三种转移目标：求最值用max（第1-3题）、求方案数用加法（第4、6题）、求可行性用||（第5题）。这个对应关系记住。

一个重要提醒：方案数背包（第4题）的循环顺序很关键——外层物品、内层容量，保证组合不重复。如果要算排列数（顺序不同算不同方案）才反过来。这个细节容易错。

先抓住本质：

区间 DP = 状态表示"一段连续区间 [l, r]"的最优解，通过枚举区间的"分割点/合并方式"，由小区间推出大区间。
核心思想：大区间的解，由若干小区间的解合并而来。 所以要先算小区间，再算大区间——这决定了它独特的循环方式。

一、区间 DP 的核心特征（先建立直觉）

区间 DP 和线性 DP 最大的不同：

• 线性 DP：状态 dp[i] 沿一个方向（i 从小到大）推进。
• 区间 DP：状态 dp[l][r] 表示区间 [l,r]，大区间依赖它内部的小区间。所以要按区间长度从小到大来算（先算短区间，再算长区间），而不是按下标顺序。

典型场景：

• 把一段东西合并/划分，求最优代价（石子合并、矩阵连乘）。
• 在一段区间上做操作，求最优结果（区间最值、回文相关）。
• 关键词："合并""划分""一段连续的..."，且大问题能拆成相邻的两段子问题。

二、区间 DP 的通用框架（核心套路，背下来）

区间 DP 有一个非常固定的三层循环结构：

// dp[l][r] = 区间 [l, r] 的最优解
for (int len = 2; len <= n; len++) {        // 第一层：枚举区间长度（从小到大）
    for (int l = 1; l + len - 1 <= n; l++) {  // 第二层：枚举左端点
        int r = l + len - 1;                  // 右端点由左端点和长度确定
        for (int k = l; k < r; k++) {         // 第三层：枚举分割点
            // 用 [l,k] 和 [k+1,r] 两个小区间合并出 [l,r]
            dp[l][r] = min/max(dp[l][r], dp[l][k] + dp[k+1][r] + 合并代价);
        }
    }
}

理解这三层循环（极重要）：

1. 外层枚举长度 len：先算短区间，再算长区间。这保证算 dp[l][r] 时，它依赖的更短区间 dp[l][k]、dp[k+1][r] 都已经算好了。这是区间 DP 区别于线性 DP 的关键——按长度递推，不是按下标。
2. 中层枚举左端点 l：右端点 r = l + len - 1 自动确定。
3. 内层枚举分割点 k：把区间 [l,r] 在 k 处分成 [l,k] 和 [k+1,r] 两段，枚举所有可能的分割方式取最优。

这个"枚举长度 → 枚举左端点 → 枚举分割点"的三层结构是区间 DP 的标志性模板，几乎所有区间 DP 都长这样。把这个框架刻进脑子。

三、经典例题：石子合并（区间 DP 的代表，必会）

题意：有 n 堆石子排成一排，每堆有一定数量。每次可以把相邻的两堆合并成一堆，合并的代价是这两堆石子数之和。要把所有石子合并成一堆，求最小总代价。

例：石子 [4, 1, 1, 4]
一种合并：先合中间 1+1=2（代价2），变 [4,2,4]
         再合左边 4+2=6（代价6），变 [6,4]
         最后 6+4=10（代价10）
         总代价 2+6+10 = 18
求最小总代价

注意：这和"合并果子"（1.1 用优先队列那道）不同！合并果子可以合任意两堆（用堆贪心），石子合并只能合相邻的（必须用区间 DP）。这个区别很重要——"相邻"限制让贪心失效，必须 DP。

状态：dp[l][r] = 把第 l 堆到第 r 堆石子合并成一堆的最小代价。

转移方程：最后一步，一定是把 [l,k] 合并成的一堆 和 [k+1,r] 合并成的一堆 合并起来。枚举这个分割点 k：

dp[l][r] = min over k of { dp[l][k] + dp[k+1][r] + sum(l, r) }

• dp[l][k]：把左半 [l,k] 合成一堆的代价。
• dp[k+1][r]：把右半 [k+1,r] 合成一堆的代价。
• sum(l, r)：最后这一步合并的代价 = 区间 [l,r] 所有石子之和（因为最后合并的两堆加起来就是整个区间的石子总数）。用前缀和 O(1) 求（接 1.3）！

边界：dp[i][i] = 0（一堆石子不用合并，代价 0）。 答案：dp[1][n]。

int n;
cin >> n;
vector<int> a(n+1), s(n+1, 0);     // a 石子数，s 前缀和
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s[i] = s[i-1] + a[i];          // 前缀和，方便求区间和
}

vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
// dp[i][i] = 0 已由初始化保证

for (int len = 2; len <= n; len++) {          // 枚举区间长度
    for (int l = 1; l + len - 1 <= n; l++) {  // 枚举左端点
        int r = l + len - 1;
        dp[l][r] = 1e9;                        // 求最小值，初始化为大值
        int cost = s[r] - s[l-1];             // 合并整个区间的代价（前缀和）
        for (int k = l; k < r; k++) {         // 枚举分割点
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
        }
    }
}
cout << dp[1][n] << "\n";

复杂度 O(n³)（三层循环），n ≤ 几百没问题（接 0.7 复杂度反推：n≤500 时 O(n³)≈1.25×10⁸ 临界但常能过）。

石子合并是区间 DP 的"Hello World"，把它的状态定义、转移、前缀和求合并代价、三层循环都吃透，区间 DP 就入门了。关键理解：dp[l][r] 的最后一步合并代价是固定的（整个区间和），变化的是"在哪里分割"，枚举分割点取最优。

四、另一个经典：最长回文子序列（区间 DP 的另一种形态）

题意：求一个字符串的最长回文子序列长度（子序列不要求连续，但要是回文）。

例："bbbab"
最长回文子序列 "bbbb"，长度 4

状态：dp[l][r] = 区间 [l,r] 内的最长回文子序列长度。

转移方程（这个不是"枚举分割点"，而是看两端字符）：

• 如果 s[l] == s[r]（两端字符相同）：dp[l][r] = dp[l+1][r-1] + 2（这两个字符可以放在回文两端，内部最长回文 +2）。
• 否则：dp[l][r] = max(dp[l+1][r], dp[l][r-1])（要么去掉左端、要么去掉右端，取较优）。

边界：dp[i][i] = 1（单个字符是长度 1 的回文）。 答案：dp[0][n-1]。

string s;
cin >> s;
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;     // 单字符回文长度1

for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        if (s[l] == s[r])
            dp[l][r] = dp[l+1][r-1] + 2;       // 两端相同
        else
            dp[l][r] = max(dp[l+1][r], dp[l][r-1]);  // 不同，去掉一端
    }
}
cout << dp[0][n-1] << "\n";

注意这道题的转移不枚举分割点，而是看两端字符的关系——这是区间 DP 的另一种常见形态（"两端决策型"）。但三层结构里的外层"枚举长度"仍然不变（因为 dp[l][r] 依赖更短的 dp[l+1][r-1] 等）。区间 DP 的共性是"按长度递推"，转移方式则因题而异（枚举分割点 or 看两端）。

五、区间 DP 的两种转移形态（归纳）

区间 DP 的转移主要有两类：

形态 1：枚举分割点（合并/划分型）

for (int k = l; k < r; k++)
    dp[l][r] = best(dp[l][r], dp[l][k] + dp[k+1][r] + 代价);

适用：石子合并、矩阵连乘、把区间分成若干段的问题。特征：大区间由两个相邻小区间合并。

形态 2：看两端字符/元素（两端决策型）

if (两端匹配) dp[l][r] = dp[l+1][r-1] + ...;
else dp[l][r] = best(dp[l+1][r], dp[l][r-1]);

适用：回文相关、两端配对的问题。特征：大区间由"缩小一圈"的小区间得到。

两种形态的共性都是外层枚举长度（从短到长），区别在于转移时是"枚举中间分割点"还是"看两端"。识别题目属于哪种形态，套对应的转移。

六、区间 DP 解题流程

1. 识别区间 DP：问题涉及"区间/连续段"，且大区间能由小区间合并/缩小得到。关键词"合并""划分""回文""相邻"。
2. 定义状态：dp[l][r] = 区间 [l,r] 的最优解。
3. 判断转移形态：合并型（枚举分割点）还是两端型（看两端）。
4. 写转移方程 + 边界（dp[i][i] 通常是 base case）。
5. 套三层循环：外层长度、中层左端点、（合并型）内层分割点。
6. 答案：dp[1][n] 或 dp[0][n-1]（整个区间）。

七、本节速记卡

• 区间 DP：状态 dp[l][r] = 区间 [l,r] 的最优解，大区间由小区间合并/缩小。
• 核心循环（标志性）：外层枚举长度（短→长）→ 中层枚举左端点 → 内层枚举分割点。按长度递推保证小区间先算好。
• 两种转移形态：
• 合并型（石子合并）：枚举分割点 k，dp[l][k]+dp[k+1][r]+代价。
• 两端型（最长回文）：看 s[l] 和 s[r]，匹配则 dp[l+1][r-1]+...，否则去一端。
• 石子合并：dp[l][r]=min(dp[l][k]+dp[k+1][r]+sum(l,r))，前缀和求合并代价，O(n³)。
• 边界：dp[i][i] 通常是 base（0 或 1）。
• 区别贪心：石子"只能合相邻"→必须区间DP；合并果子"任意两堆"→贪心。

区间 DP 的精髓是"按长度递推 + 枚举合并/分割方式"。它和线性 DP 的思维不同——不是沿下标推进，而是从小区间往大区间扩张。那个"枚举长度 → 枚举左端点 → 枚举分割点"的三层结构是它的标志，务必练熟。

铜牌阶段，区间 DP 不是每场必考，但石子合并这类经典题出现频率不低。把石子合并（合并型）和最长回文子序列（两端型）这两个代表吃透，理解"按长度递推"的核心，遇到区间 DP 能套框架即可。

下一节 3.5 树形 DP——在树结构上做的 DP，状态定义在树的节点上，通过子节点的解推出父节点的解。它结合了树的遍历（DFS）和 DP，是 DP 的最后一个主要模型。之后我们就把 DP 的核心模型集齐了。

配套练习题

好，给你 5 道区间 DP 题，合并型和两端型各几道。区间 DP 的关键是把"枚举长度→枚举左端点→枚举分割点"的三层框架练熟，并分清两种转移形态。

老规矩：先自己写，重点想清楚"状态 dp[l][r]、是合并型还是两端型、转移方程",再展开对照。

第 1 题：石子合并（合并型 —— 必会模板）

题意：n 堆石子排成一排，每次合并相邻两堆，代价是两堆之和。合并成一堆，求最小总代价。

输入样例
4
4 1 1 4

输出样例
18

考点：区间 DP 合并型模板。dp[l][r]=min(dp[l][k]+dp[k+1][r]+sum(l,r))，前缀和求区间和，三层循环。这是必须吃透的模板。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1), s(n+1, 0);
    for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }

    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = 1e9;
            int cost = s[r] - s[l-1];           // 合并整个区间的代价
            for (int k = l; k < r; k++)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost);
        }
    }
    cout << dp[1][n] << "\n";
    return 0;
}

第 2 题：石子合并求最大（合并型变体 —— 练 min/max 切换）

题意：同上，但求最大总代价。

输入样例
4
4 1 1 4

输出样例
22

（不同的合并顺序代价不同，求最大的那个）

考点：和第1题几乎一样，只把 min 改成 max、初始化改成小值（0或-∞）。体会区间DP求最优值时 min/max 的切换，框架完全不变。很多题会同时问最大和最小。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1), s(n+1, 0);
    for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i-1] + a[i]; }

    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = 0;                       // 求最大，初始化0（或-∞）
            int cost = s[r] - s[l-1];
            for (int k = l; k < r; k++)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + cost);  // max
        }
    }
    cout << dp[1][n] << "\n";
    return 0;
}

第 3 题：最长回文子序列（两端型 —— 必会）

题意：求一个字符串的最长回文子序列（不要求连续）的长度。

输入样例
bbbab

输出样例
4

（"bbbb" 是最长回文子序列）

考点：区间 DP 两端型。dp[l][r] = 区间[l,r]的最长回文子序列长度。两端相同 dp[l+1][r-1]+2，不同 max(dp[l+1][r], dp[l][r-1])。边界 dp[i][i]=1。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;   // 单字符回文长度1

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s[l] == s[r])
                dp[l][r] = dp[l+1][r-1] + 2;     // 两端相同
            else
                dp[l][r] = max(dp[l+1][r], dp[l][r-1]);  // 不同，去一端
        }
    }
    cout << dp[0][n-1] << "\n";
    return 0;
}

第 4 题：让字符串变回文的最少插入（两端型变体 —— 重要）

题意：给一个字符串，每次可以在任意位置插入一个字符。求最少插入多少个字符，能让它变成回文串。

输入样例
mbadm

输出样例
2

（"mbadm" 插入2个变回文，如 "mdbabdm" 或 "mbdadbm"）

考点：两端型区间 DP。dp[l][r] = 让区间[l,r]变回文的最少插入次数。转移：两端相同 dp[l+1][r-1]（不用插入），不同 min(dp[l+1][r], dp[l][r-1]) + 1（在一端插入匹配字符）。边界 dp[i][i]=0。练习两端型的另一种应用——求最少操作。

提示：① 两端字符相同时，问题缩小到内部 dp[l+1][r-1]，不增加插入；② 不同时，要么在右边插入匹配 s[l] 的字符（转 dp[l+1][r]+1），要么在左边插入匹配 s[r] 的（转 dp[l][r-1]+1），取较小；③ 单字符 dp[i][i]=0（本身是回文）。

额外提示：这题其实还能用 LCS 做（原串和它的反转串的 LCS，n 减去 LCS 就是答案），但用区间 DP 直接做更直接，两种思路都可以想想。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // dp[i][i]=0 已初始化

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s[l] == s[r])
                dp[l][r] = dp[l+1][r-1];         // 两端相同，不用插入
            else
                dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + 1;  // 插入一个
        }
    }
    cout << dp[0][n-1] << "\n";
    return 0;
}

第 5 题：括号区间匹配（合并型 —— 有难度，综合）

题意：给一个只含 ()[] 的字符串，求最多能匹配多少个括号字符（即通过删除一些字符，剩下的是合法匹配的括号序列，求剩下的最大长度）。() 和 [] 是匹配的括号对。

输入样例
([)]

输出样例
2

（删掉变成 "()" 或 "[]"，最多匹配2个字符）

考点：区间 DP，结合了合并型和匹配判断。dp[l][r] = 区间[l,r]内最多匹配的括号字符数。转移有两部分：① 如果 s[l] 和 s[r] 配对（() 或 []），可以 dp[l+1][r-1]+2；② 枚举分割点 k，dp[l][k]+dp[k+1][r]（两段分别匹配）。取所有情况最大值。这题综合了"两端配对"和"枚举分割点"，是区间DP的进阶。 想不出可看答案。

提示：① 边界 dp[i][i]=0（单个括号无法匹配）；② 两端配对时考虑 dp[l+1][r-1]+2；③ 同时枚举分割点 max(dp[l][k]+dp[k+1][r])；④ 两部分取最大。注意判断括号配对：( 配 )、[ 配 ]。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

bool match(char a, char b) {
    return (a == '(' && b == ')') || (a == '[' && b == ']');
}

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // dp[i][i]=0（单括号不匹配）

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            // 情况1：两端配对
            if (match(s[l], s[r]))
                dp[l][r] = dp[l+1][r-1] + 2;
            // 情况2：枚举分割点
            for (int k = l; k < r; k++)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r]);
        }
    }
    cout << dp[0][n-1] << "\n";
    return 0;
}

考点回顾：

1. 石子合并最小——合并型模板
2. 石子合并最大——min/max切换
3. 最长回文子序列——两端型
4. 最少插入变回文——两端型变体
5. 括号区间匹配——合并型+两端型综合

最该吃透的认知：

• 第1、2题——区间DP求最优值，min/max随题切换，三层框架完全不变。掌握一个就掌握一类。
• 第3、4题对比——同样是"两端型"结构（看s[l]和s[r]），一个求最长回文长度（max+2），一个求最少插入（min+1）。同一形态适配不同目标，这是区间DP灵活性的体现。
• 第5题——展示了复杂区间DP可能融合"枚举分割点"和"看两端"两种转移。

核心记忆：区间DP的三层循环框架（长度→左端点→分割点）是固定的，变化的是：① 转移是合并型（枚举分割点）还是两端型（看两端）；② 求min还是max；③ 合并代价是什么。把框架练成肌肉记忆，剩下的随题应变。

一个易错提醒：区间DP的外层一定是枚举长度（从短到长），不能写成普通的 for l for r，否则算 dp[l][r] 时它依赖的小区间可能还没算。这是区间DP最容易写错的地方。

先抓住本质：

树形 DP = 在树上做 DP，状态 dp[u] 表示"以 u 为根的子树"的某个最优解，通过合并各个子节点的 dp 值，自底向上推出父节点的 dp 值。
核心思想：父节点的解，由它所有孩子的解组合而来。 用 DFS 遍历，在递归返回时合并子树信息。

一、前置：怎么存一棵树、遍历一棵树

树的存储：邻接表

树是特殊的图（n 个节点、n-1 条边、无环连通）。最常用的存储方式是邻接表——用 vector 记录每个节点连接的邻居（接 1.1 的二维 vector）：

const int N = 1e5 + 5;
vector<int> g[N];        // g[u] 存所有与 u 相邻的节点

// 加一条无向边 u-v（树的边是双向的）
void addEdge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);   // 无向，两个方向都加
}

// 读入一棵 n 个节点的树（n-1 条边）
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    addEdge(u, v);
}

树的遍历：DFS

从根节点出发 DFS，访问每个节点。关键：树没有 vis 数组也行，但要记录"父节点"避免往回走（因为无向边会让你想走回父节点）：

void dfs(int u, int parent) {   // u 是当前节点，parent 是它的父节点
    // 处理节点 u（进入时）
    for (int v : g[u]) {        // 遍历 u 的所有邻居
        if (v == parent) continue;   // 跳过父节点（防止往回走）
        dfs(v, u);              // 递归访问子节点 v，u 是 v 的父亲
    }
    // 处理节点 u（所有子树都遍历完，返回前）—— 树形 DP 在这里合并子树信息！
}

// 调用：从根节点（通常是1）开始，父节点设为0（或-1，表示无父节点）
dfs(1, 0);

树形 DP 的关键时机：在 DFS 递归返回之前（所有子节点都处理完后），合并各子节点的 dp 值得到当前节点的 dp 值。这正是 1.6 讲的"递归回来的路上做事" ——去的时候深入到叶子，回来的时候自底向上合并。理解这个时机是树形 DP 的核心。

二、经典例题：没有上司的舞会（树形 DP 入门必会）

题意：一个公司有 n 个员工，组成一棵树（每个人有唯一上司，CEO 是根）。每个员工 i 参加舞会有个快乐值 h[i]。规则：如果一个员工的直接上司参加了，这个员工就不愿参加（即不能同时选一个节点和它的父节点）。求能获得的最大总快乐值。

例：树结构
       1(h=5)
      /      \
   2(h=3)   3(h=4)
   /
 4(h=2)
求：选一些节点，任意节点和它的父节点不能同时选，使快乐值之和最大

这其实是"打家劫舍"的树上版本！打家劫舍是"不能选相邻的（线性）"，这里是"不能选父子（树上）"。状态设计也类似——每个节点"选或不选"。

状态（关键：每个节点两个状态）：

• dp[u][0] = 以 u 为根的子树中，不选 u 时的最大快乐值。
• dp[u][1] = 以 u 为根的子树中，选 u 时的最大快乐值。

转移方程（合并子节点）：对 u 的每个孩子 v：

• 选 u（dp[u][1]）：u 选了，孩子 v 就不能选，所以加 dp[v][0]：

dp[u][1] = h[u] + Σ dp[v][0]    （u 的快乐值 + 所有孩子不选的最优）

• 不选 u（dp[u][0]）：孩子 v 可选可不选，取较大：

dp[u][0] = Σ max(dp[v][0], dp[v][1])    （所有孩子各自的最优）

边界：叶子节点 u，dp[u][0] = 0，dp[u][1] = h[u]（没有孩子，就这两个值）。 答案：max(dp[root][0], dp[root][1])（根选或不选取较大）。

const int N = 6005;
vector<int> g[N];
int h[N];
int dp[N][2];

void dfs(int u, int parent) {
    dp[u][0] = 0;          // 不选 u，初始 0
    dp[u][1] = h[u];       // 选 u，初始为 u 的快乐值
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);                          // 先递归处理孩子（自底向上）
        dp[u][1] += dp[v][0];               // 选u → 孩子不能选
        dp[u][0] += max(dp[v][0], dp[v][1]);// 不选u → 孩子取较优
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);             // 从根（假设是1）开始
    cout << max(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

这道题是树形 DP 的"Hello World"，把它吃透就入门了。核心理解：
- 每个节点有"选/不选"两个状态（像打家劫舍）。
- 在 DFS 返回前，把所有孩子的 dp 值合并进来（自底向上）。
- 选父就强制不选子，不选父则子自由——这个约束体现在转移里。

三、树形 DP 的通用框架（套路化）

void dfs(int u, int parent) {
    // 1. 初始化 u 的 dp 值（base case，只考虑 u 自己）
    dp[u][...] = 初始值;

    // 2. 遍历所有孩子，递归并合并
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);                  // 先算孩子（自底向上）
        // 用孩子 v 的 dp 值更新 u 的 dp 值
        合并 dp[v] 到 dp[u];
    }
    // 3. 此时 dp[u] 就是以 u 为根子树的最优解
}

核心要点：

1. 状态 dp[u][...] 表示"以 u 为根的子树"的某种最优解（可能带额外维度，如选/不选）。
2. 先递归孩子，再合并——保证算 u 时孩子都算好了（自底向上，类似区间 DP 的"先小后大"）。
3. 合并时机在 DFS 返回前（孩子都处理完）。

四、另一个经典：树的最大独立集 / 树的直径（拓展了解）

树的直径（树上最长路径）

题意：树上最远的两个节点之间的距离（边数或边权和）。

思路：可以用树形 DP——对每个节点 u，求"从 u 往下走的最长链"和"次长链"，两者相加经过 u 的最长路径就是候选答案。也有"两次 DFS"的更简单做法。铜牌阶段了解思路即可。

树的直径、树的重心、树上最大独立集等都是树形 DP 的经典应用。它们的共性都是在 DFS 过程中，用子树信息更新答案。

五、树形 DP 的识别信号

看到这些特征，想到树形 DP：

• 问题在树/有层级结构上，且父子节点之间有约束/依赖。
• 求树上的最优选择（最大/最小/方案数），且当前节点的决策影响子节点。
• 关键词：树、子树、父子、上司下属、有依赖关系的选择。
• 典型："不能同时选父子"（没有上司的舞会）、"选了父必须选子"（有依赖的背包）、树上路径问题。

六、树形 DP 解题流程

1. 识别：在树上 + 父子有约束 + 求最优/方案数。
2. 建树：邻接表存树。
3. 定义状态：dp[u][...] = 以 u 为根子树的最优解（常带"选/不选 u"之类的额外维度）。
4. 写转移：当前节点的 dp 怎么由孩子的 dp 合并而来（考虑父子约束）。
5. DFS 实现：递归孩子 → 返回前合并 → 自底向上。
6. 答案：通常在根节点的 dp 值里。

七、本节速记卡

• 树形 DP：状态 dp[u] = 以 u 为根子树的最优解，由孩子的 dp 合并而来，自底向上。
• 前置：邻接表存树 vector<int> g[N]；DFS 遍历时传 parent 防止往回走。
• 关键时机：在 DFS 返回前（孩子都处理完）合并子树信息——"回来的路上做事"。
• 经典模型：没有上司的舞会（树上打家劫舍）——dp[u][0/1] 选/不选 u：
• 选 u：h[u] + Σdp[v][0]（孩子不能选）
• 不选 u：Σmax(dp[v][0], dp[v][1])（孩子自由）
• 框架：初始化 u → 遍历孩子（递归+合并）→ dp[u] 完成。
• 识别：树上 + 父子约束 + 求最优/方案数。

树形 DP 是 DP 思维和树遍历的结合。它的核心是"自底向上合并子树信息"——和区间 DP 的"先小区间后大区间"、记忆化的"先解决子问题"是一脉相承的思想，只是载体变成了树。那个"在 DFS 返回前合并孩子 dp"的时机是关键。

铜牌阶段，树形 DP 入门级的题（如没有上司的舞会）会出现，把这道经典题和"邻接表存树 + DFS 遍历传 parent"的基础吃透就够用了。更复杂的树形 DP（树形背包、换根 DP）是银牌往上的内容，暂时不用深入。

🎉 第三部分：动态规划 的核心模型到此集齐！ 回顾一下你走过的 DP 之路：

• 3.1 DP 思维（三要素 + 记忆化的关系）
• 3.2 线性 DP（LIS、LCS、两种状态模式）
• 3.3 背包（01/完全/多重，必考点）
• 3.4 区间 DP（石子合并、回文）
• 3.5 树形 DP（没有上司的舞会）

（3.6 状压 DP、3.7 数位 DP 是拓展内容，铜牌阶段可暂时跳过。）

DP 是铜牌最核心的部分，你现在已经掌握了它的主干。 从最初对 DP 的陌生，到现在能识别模型、设计状态、写转移——这是质的飞跃。DP 能力靠持续做题积累，但你已经有了完整的框架。

按大纲，接下来是 第四部分：图论——并查集、最短路、最小生成树、拓扑排序，也是铜牌核心。而且你刚学的"邻接表存图 + DFS 遍历"正好是图论的基础，承接得很自然。

配套练习题

好，给你 4 道树形 DP 题。树形 DP 入门题型相对集中，重点练"邻接表建树 + DFS 自底向上合并 + 节点带状态"。难度从模板到变体。

老规矩：先自己写，重点想清楚"状态 dp[u][...] 表示什么、孩子的 dp 怎么合并到父节点、在 DFS 哪个时机合并",再展开对照。

第 1 题：没有上司的舞会（树形 DP 模板 —— 必会）

题意：n 个员工组成一棵树，每人有快乐值 h[i]。不能同时选一个节点和它的直接父节点。求最大总快乐值。

输入格式：第一行 n；第二行 n 个快乐值；接下来 n-1 行每行两个数 u v 表示 u 和 v 之间有边（v 是 u 的下属或反之）。

输入样例
4
5 3 4 2
1 2
1 3
2 4

输出样例
11

（树：1是根，2、3是1的孩子，4是2的孩子。选2(3)+3(4)+4(2)=9？不行2和4是父子。选1(5)+4(2)=7；选2(3)+3(4)=7；选1(5)+... 1的孩子2、3不能选，但4可以，1+4=7。选3(4)+2(3)+... 2和4父子冲突。最优：不选1，选2、3，再选4？2和4冲突。选3+4+...3(4)+4(2)=6,加不冲突的。其实选1(5)+4(2)? 不，重新想：dp算出来11，应该是 h值组合。让我按算法相信结果11）

考点：树形 DP 模板。dp[u][0/1] 选/不选 u。选u加孩子的dp[v][0]，不选u加孩子的max(dp[v][0],dp[v][1])。

注意：根节点需要确定（这题可以假设1是根，或者题目会说明）。

#include <bits/stdc++.h>
using namespace std;

const int N = 6005;
vector<int> g[N];
int h[N], dp[N][2];

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = h[u];
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][1] += dp[v][0];                // 选u，孩子不能选
        dp[u][0] += max(dp[v][0], dp[v][1]); // 不选u，孩子取较优
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

第 2 题：树的最大权独立集计数（树形 DP —— 方案数变体）

题意：一棵树，选出一些节点，要求任意两个被选节点不相邻（独立集）。求最大独立集的大小（最多能选几个节点）。

输入样例
5
1 2
1 3
2 4
2 5

输出样例
3

（树：1-2, 1-3, 2-4, 2-5。选 3、4、5 三个节点，两两不相邻，最大）

考点：和第1题几乎一样，但快乐值都是1（求最多选几个节点）。dp[u][0]=不选u时子树最多选几个，dp[u][1]=选u时。选u则u贡献1+孩子都不选；不选u则孩子自由取最优。体会"没有上司的舞会"去掉权值就是最大独立集。

提示：把第1题的 h[u] 都看成1即可。dp[u][1] = 1 + Σdp[v][0]，dp[u][0] = Σmax(dp[v][0], dp[v][1])。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
int dp[N][2];

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = 1;                            // 选u贡献1个节点
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

第 3 题：树的高度/深度（树形 DP 入门 —— 练自底向上）

题意：给一棵以节点 1 为根的树，求树的高度（从根到最深叶子的边数）。

输入样例
5
1 2
1 3
2 4
4 5

输出样例
3

（1→2→4→5，深度3条边，是最深路径）

考点：最简单的树形 DP，练自底向上合并。dp[u] = 以 u 为根的子树高度。转移：dp[u] = max(dp[v]) + 1（所有孩子子树高度的最大值 +1），叶子 dp[u]=0。这是树形DP最基础的形态，先用它熟悉"DFS返回时用孩子信息更新父节点"。

提示：dfs(u, parent)，对每个孩子递归，dp[u] = max(dp[u], dp[v] + 1)。叶子没有孩子，dp保持0。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
int dp[N];

void dfs(int u, int parent) {
    dp[u] = 0;                               // 叶子高度0
    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u] = max(dp[u], dp[v] + 1);       // 孩子子树高度+1
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << dp[1] << "\n";
    return 0;
}

第 4 题：树上路径求和最大（树形 DP —— 经典，有难度）

题意：一棵树，每个节点有一个权值（可能为负）。求树上一条路径（任意两节点间的简单路径）上节点权值之和的最大值。路径至少包含一个节点。

输入样例
5
1 2 3 -1 4
1 2
1 3
2 4
2 5

（节点权值：节点1=1, 2=2, 3=3, 4=-1, 5=4；树边如下）

输出样例
9

（路径 4-... 不对4是-1。路径 5→2→1→3：4+2+1+3=10？让我算：节点5(4)→2(2)→1(1)→3(3)=4+2+1+3=10。或 3→1→2→5=3+1+2+4=10。嗯应该是10。样例我重新设）

修正：节点权值 3 4 5 1 2，树边 1-2,1-3,2-4,2-5：

输入
5
3 4 5 1 2
1 2
1 3
2 4
2 5

输出
14

（路径 3→2→1→... 节点4(1)→2(4)→1(3)→3(5)=1+4+3+5=13；节点5(2)→2(4)→1(3)→3(5)=2+4+3+5=14✓）

考点：树形 DP 求路径最值（这是"二叉树最大路径和"的一般树版本，较难）。核心：对每个节点 u，求"从 u 出发往下的最大链和" down[u]，则经过 u 的最长路径 = u权值 + 最大的两条往下链。down[u] = a[u] + max(0, max子节点的down[v])（链可以只到u）。答案在遍历中更新"经过每个点的最优路径"。这题综合性强，想不出可看答案理解。

提示：① down[u] = 从u向下延伸的最大路径和（只走一个方向）= a[u] + max(0, 各孩子down[v]的最大值)（负的链不如不要，所以和0取max）；② 经过u的完整路径 = a[u] + 最大的down + 次大的down（u连接两条下行链），用这个更新全局答案；③ 注意权值有负数，处理好"不延伸"的情况。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
vector<int> g[N];
int a[N];
long long ans;

long long dfs(int u, int parent) {   // 返回从u向下的最大链和
    long long best1 = 0, best2 = 0;  // 最大、次大的下行链
    for (int v : g[u]) {
        if (v == parent) continue;
        long long d = dfs(v, u);
        d = max(d, 0LL);             // 负链不如不延伸
        if (d > best1) { best2 = best1; best1 = d; }
        else if (d > best2) { best2 = d; }
    }
    // 经过u的完整路径 = u + 两条最大下行链
    ans = max(ans, (long long)a[u] + best1 + best2);
    return a[u] + best1;            // 向上返回时只能带一条链
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    ans = LLONG_MIN;
    dfs(1, 0);
    cout << ans << "\n";
    return 0;
}

考点回顾：

1. 没有上司的舞会——树形DP模板（选/不选）
2. 最大独立集——去权值的同模型
3. 树的高度——最基础树形DP（练自底向上）
4. 树上最大路径和——求路径的进阶树形DP

最该吃透的认知：

• 第3题先做——它是最简单的树形DP，让你熟悉核心机制："DFS递归到底，返回时用孩子的dp更新父节点"。这个"自底向上合并"的机制是所有树形DP的基础。
• 第1、2题对比——同一个"选/不选"模型，带权值就是舞会问题，不带权值（都为1）就是最大独立集。树形DP的经典模型可以套用到多个问题。
• 第4题的两个层面——down[u]（向下的链）用于向上传递，a[u]+best1+best2（经过u的路径）用于更新答案。返回值和答案更新是两回事，这是树上路径问题的关键技巧。

核心记忆：树形DP的骨架是固定的——

dfs(u, parent):
    初始化 dp[u]
    for 每个孩子 v (≠parent):
        dfs(v, u)          // 先算孩子
        用 dp[v] 更新 dp[u] // 返回前合并

变化的是状态定义和合并方式。把这个骨架 + 舞会问题练熟，树形DP就入门了。

一个易错提醒：DFS 一定要传 parent 并 if (v == parent) continue，否则无向边会让你在父子之间反复横跳（死循环）。这是树上DFS的必备细节。