# 动态规划 (DP) 模块讲义

欢迎来到算法中最烧脑、也最迷人的模块——**动态规划 (Dynamic Programming, 简称 DP)**。

### 什么是动态规划？
如果说普通算法是“走一步算一步”，那么动态规划就是**“记住过去，规划未来”**。
* **核心思想**：把一个大问题拆成几个相似的小问题。如果小问题的答案被算过了，我们就把它记在小本本上（**状态与状态转移**），下次直接抄答案，避免重复计算，从而把指数级的暴力搜索降维打击到多项式时间。

本模块包含 **背包问题、线性 DP、区间 DP、计数类 DP、数位统计 DP、状态压缩 DP、树形 DP、记忆化搜索** 共 8 个核心 DP 模型。

---

## 1. 背包问题 (Knapsack Problems)

背包问题是 DP 的入门敲门砖，主要分为四种经典模型：

### ① 01 背包
* **模型**：有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。**每件物品只有 1 个**，选择放或不放，怎么让总价值最大？
* **状态表示**：$dp[j]$ 表示容量为 $j$ 的背包所能装下的最大价值。
* **核心代码（注意必须逆序循环）**：
  ```cpp
  for (int i = 1; i <= n; i++)
      for (int j = V; j >= v[i]; j--) // 必须从大到小，防止重复使用物品
          dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
  ```

### ② 完全背包
* **模型**：每种物品有**无限个**。
* **核心代码（正序循环）**：
  ```cpp
  for (int i = 1; i <= n; i++)
      for (int j = v[i]; j <= V; j++) // 从小到大，允许物品被重复选多次
          dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
  ```

### ③ 多重背包
* **模型**：每种物品有固定的数量（比如第 $i$ 件物品最多有 $s_i$ 个）。
* **优化策略**：可以通过**二进制拆分**把多个同种物品拆成几堆（例如 13 个拆成 1, 2, 4, 6），转化成 01 背包求解。

### ④ 分组背包
* **模型**：物品被分成了 $N$ 组，每组里面有若干个互斥的物品，**每组只能挑一个**。
* **状态转移**：在 01 背包的基础上，多加一层循环枚举选组里的哪一个物品。

---

## 2. 线性 DP (Linear DP)

### 概念
状态沿着一条线性方向（如数组下标、矩阵行列）推进，是最自然的 DP。

### 经典模型：最长上升子序列 (LIS)
* **题目**：给定一个长度为 $n$ 的数组，求里面最长的严格上升子序列的长度。
* **状态定义**：$dp[i]$ 表示**以第 $i$ 个数字结尾**的最长上升子序列的长度。
* **状态转移方程**：
  $$dp[i] = \max_{0 \le j < i, a[j] < a[i]} (dp[j] + 1)$$
* 代码实现：对每个 $i$，往前扫描所有比它小的 $j$，把对应的 $dp[j] + 1$ 最大值赋给 $dp[i]$。

---

## 3. 区间 DP (Interval DP)

### 概念
以**区间长度**作为 DP 的阶段，从小区间推导到大区间。

### 经典模型：石子合并
* **题目**：有 $N$ 堆石子排成一排，每次只能合并相邻的两堆，代价是两堆石子的重量和。求把所有石子合并成一堆的最小总代价。
* **状态定义**：$dp[i][j]$ 表示把从第 $i$ 堆到第 $j$ 堆石子合并成一堆的最小代价。
* **状态转移方程**：
  枚举分界点 $k$（$i \le k < j$）：
  $$dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + \text{sum}(i, j) \}$$
* **循环特点**：第一层循环枚举**区间长度**（从 2 到 $n$），第二层循环枚举**起点 $i$**。

---

## 4. 计数类 DP (Counting DP)

### 概念
求满足条件的**方案总数**（而不是求最大值或最小值），通常利用加法原理。

### 经典模型：整数划分
* **题目**：把一个正整数 $n$ 划分为若干个正整数之和，有多少种不同的分法？
* **状态转移**：它本质上是一个完全背包的变形——背包容量是 $n$，物品体积是 $1 \sim n$，求填满背包的方案数。
  $$dp[j] = dp[j] + dp[j - i]$$

---

## 5. 数位统计 DP (Digit DP)

### 概念
求在给定的区间 $[L, R]$ 内，有多少个数字满足某种特定的数位条件（例如：数字中不包含连续的 `49`）。

### 核心做法
通常结合**数位分离**与**记忆化搜索**。把数字看作一个字符串，从最高位向最低位递归填数字，分类讨论当前位能填 $0 \sim 9$ 的哪些数字，并用数组把搜过的状态存起来。

---

## 6. 状态压缩 DP (State Compression DP)

### 概念
当 DP 的状态可以用一个**二进制整数**来表示时，我们把状态压成一个数字（例如用 `1011` 表示第 0、1、3 个格子被占用，第 2 个格子空着）。

### 经典模型：小国王 / 蒙特哈密顿通路 (TSP)
* 常常结合**位运算**（如检查某一位是否为 1，两行状态是否冲突）。由于二进制状态通常是 $2^n$ 级别的，所以适用于 $n$ 比较小（如 $n \le 20$）的情况。

---

## 7. 树形 DP (Tree DP)

### 概念
在“树”这种特殊的图结构上做动态规划。因为树天然具有递归的子结构（根节点依赖子树），所以非常适合用 DFS 递归求解。

### 经典模型：没有上司的舞会
* **题目**：公司要办派对，员工有树状的上下级关系。规则是：如果员工去了，他的直属上司绝对不能去。每个人有一个“快乐指数”，求派对的最大快乐值。
* **状态定义**：
  * `dp[u][0]` 表示：以 $u$ 为根的子树中，**$u$ 不去**时的最大快乐值。
  * `dp[u][1]` 表示：以 $u$ 为根的子树中，**$u$ 去**时的最大快乐值。
* **状态转移方程**：
  * 如果 $u$ 不去，他的孩子 $v$ 可以去也可以不去：
    $$dp[u][0] += \sum \max(dp[v][0], dp[v][1])$$
  * 如果 $u$ 去了，他的孩子 $v$ 绝对不能去：
    $$dp[u][1] += \sum dp[v][0]$$

---

## 8. 记忆化搜索 (Memoized Search)

### 概念与妙处
* 有时候我们在写树形 DP 或复杂的图上 DP 时，状态转移的先后顺序很难理清楚（边界条件和前驱后继容易搞混）。
* **解法**：直接写一个普通的**递归 DFS**，但在递归入口处加一个判断：**“这个状态我以前算过没有？”**
  * 如果算过，直接返回备忘录里的答案。
  * 如果没算过，递归计算，并把结果存进备忘录里。
* **本质**：记忆化搜索 = **递归形式的动态规划**。它既有 DFS 的好写、不用关心转移顺序的优点，又有 DP 的高效率。

---

动态规划 (DP) 模块讲义

欢迎来到算法中最烧脑、也最迷人的模块——动态规划 (Dynamic Programming, 简称 DP)。

什么是动态规划？

如果说普通算法是“走一步算一步”，那么动态规划就是“记住过去，规划未来”。 * 核心思想：把一个大问题拆成几个相似的小问题。如果小问题的答案被算过了，我们就把它记在小本本上（状态与状态转移），下次直接抄答案，避免重复计算，从而把指数级的暴力搜索降维打击到多项式时间。

本模块包含 背包问题、线性 DP、区间 DP、计数类 DP、数位统计 DP、状态压缩 DP、树形 DP、记忆化搜索 共 8 个核心 DP 模型。

1. 背包问题 (Knapsack Problems)

背包问题是 DP 的入门敲门砖，主要分为四种经典模型：

① 01 背包

模型：有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。每件物品只有 1 个，选择放或不放，怎么让总价值最大？
状态表示：$dp[j]$ 表示容量为 $j$ 的背包所能装下的最大价值。
核心代码（注意必须逆序循环）： cpp for (int i = 1; i <= n; i++) for (int j = V; j >= v[i]; j--) // 必须从大到小，防止重复使用物品 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

② 完全背包

模型：每种物品有无限个。
核心代码（正序循环）： cpp for (int i = 1; i <= n; i++) for (int j = v[i]; j <= V; j++) // 从小到大，允许物品被重复选多次 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

③ 多重背包

模型：每种物品有固定的数量（比如第 $i$ 件物品最多有 $s_i$ 个）。
优化策略：可以通过二进制拆分把多个同种物品拆成几堆（例如 13 个拆成 1, 2, 4, 6），转化成 01 背包求解。

④ 分组背包

模型：物品被分成了 $N$ 组，每组里面有若干个互斥的物品，每组只能挑一个。
状态转移：在 01 背包的基础上，多加一层循环枚举选组里的哪一个物品。

2. 线性 DP (Linear DP)

概念

状态沿着一条线性方向（如数组下标、矩阵行列）推进，是最自然的 DP。

经典模型：最长上升子序列 (LIS)

题目：给定一个长度为 $n$ 的数组，求里面最长的严格上升子序列的长度。
状态定义：$dp[i]$ 表示以第 $i$ 个数字结尾的最长上升子序列的长度。
状态转移方程： $$dp[i] = \max_{0 \le j < i, a[j] < a[i]} (dp[j] + 1)$$
代码实现：对每个 $i$，往前扫描所有比它小的 $j$，把对应的 $dp[j] + 1$ 最大值赋给 $dp[i]$。

3. 区间 DP (Interval DP)

概念

以区间长度作为 DP 的阶段，从小区间推导到大区间。

经典模型：石子合并

题目：有 $N$ 堆石子排成一排，每次只能合并相邻的两堆，代价是两堆石子的重量和。求把所有石子合并成一堆的最小总代价。
状态定义：$dp[i][j]$ 表示把从第 $i$ 堆到第 $j$ 堆石子合并成一堆的最小代价。
状态转移方程：枚举分界点 $k$（$i \le k < j$）： $$dp[i][j] = \min_{i \le k < j} { dp[i][k] + dp[k+1][j] + \text{sum}(i, j) }$$
循环特点：第一层循环枚举区间长度（从 2 到 $n$），第二层循环枚举起点 $i$。

4. 计数类 DP (Counting DP)

概念

求满足条件的方案总数（而不是求最大值或最小值），通常利用加法原理。

经典模型：整数划分

题目：把一个正整数 $n$ 划分为若干个正整数之和，有多少种不同的分法？
状态转移：它本质上是一个完全背包的变形——背包容量是 $n$，物品体积是 $1 \sim n$，求填满背包的方案数。 $$dp[j] = dp[j] + dp[j - i]$$

5. 数位统计 DP (Digit DP)

概念

求在给定的区间 $[L, R]$ 内，有多少个数字满足某种特定的数位条件（例如：数字中不包含连续的 49）。

核心做法

通常结合数位分离与记忆化搜索。把数字看作一个字符串，从最高位向最低位递归填数字，分类讨论当前位能填 $0 \sim 9$ 的哪些数字，并用数组把搜过的状态存起来。

6. 状态压缩 DP (State Compression DP)

概念

当 DP 的状态可以用一个二进制整数来表示时，我们把状态压成一个数字（例如用 1011 表示第 0、1、3 个格子被占用，第 2 个格子空着）。

经典模型：小国王 / 蒙特哈密顿通路 (TSP)

常常结合位运算（如检查某一位是否为 1，两行状态是否冲突）。由于二进制状态通常是 $2^n$ 级别的，所以适用于 $n$ 比较小（如 $n \le 20$）的情况。

7. 树形 DP (Tree DP)

概念

在“树”这种特殊的图结构上做动态规划。因为树天然具有递归的子结构（根节点依赖子树），所以非常适合用 DFS 递归求解。

经典模型：没有上司的舞会

题目：公司要办派对，员工有树状的上下级关系。规则是：如果员工去了，他的直属上司绝对不能去。每个人有一个“快乐指数”，求派对的最大快乐值。
状态定义：
dp[u][0] 表示：以 $u$ 为根的子树中，$u$ 不去时的最大快乐值。
dp[u][1] 表示：以 $u$ 为根的子树中，$u$ 去时的最大快乐值。
状态转移方程：
如果 $u$ 不去，他的孩子 $v$ 可以去也可以不去： $$dp[u][0] += \sum \max(dp[v][0], dp[v][1])$$
如果 $u$ 去了，他的孩子 $v$ 绝对不能去： $$dp[u][1] += \sum dp[v][0]$$

8. 记忆化搜索 (Memoized Search)

概念与妙处

有时候我们在写树形 DP 或复杂的图上 DP 时，状态转移的先后顺序很难理清楚（边界条件和前驱后继容易搞混）。
解法：直接写一个普通的递归 DFS，但在递归入口处加一个判断：“这个状态我以前算过没有？”
如果算过，直接返回备忘录里的答案。
如果没算过，递归计算，并把结果存进备忘录里。
本质：记忆化搜索 = 递归形式的动态规划。它既有 DFS 的好写、不用关心转移顺序的优点，又有 DP 的高效率。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com