🧠 一、动态规划的本质与核心思想
动态规划是一种用于求解最优子结构问题的算法思想。
一句话总结：
DP = 递推 + 记忆 + 最优子结构 + 无后效性
通俗理解：
- 你要解决一个大问题；
- 它可以分解为若干相似但更小的子问题；
- 子问题的解可以组合成大问题的解；
- 每个子问题只需求一次（通过数组或哈希表存下来）。
📚 二、DP 的分类总览
DP可以按照不同维度来分类。我们最常用的划分有以下几种：
分类维度 | 主要类型 | 举例 |
按结构 | 线性DP、区间DP、背包DP、树形DP、状态压缩DP、数位DP、记忆化搜索DP、图上DP | 最长上升子序列、石子合并、0/1背包、树上选点、旅行商、数位统计、博弈问题 |
按目标 | 最值类、计数类、可行性类、方案数类 | 最短路、路径计数、能否分割 |
按维度 | 一维、二维、多维 | LIS、编辑距离、双背包问题 |
按时间方向 | 前向DP、后向DP | 股票买卖、路径规划 |
按思路来源 | 递推式、记忆化DFS、图论DP | 拓扑序DP、区间划分DP |
我们逐一讲解每种类型。
🧩 三、线性 DP（Linear DP）
定义
问题的状态呈“线性”顺序依赖，比如第 i 个状态只依赖前面某些状态。
常见特征：一个序列或数组，状态转移沿着下标方向。
典型模型一：最长上升子序列 (LIS)
问题
给定数组
nums，找出最长上升子序列的长度。思路
dp[i] = 以 nums[i] 结尾的最长上升子序列长度 dp[i] = max(dp[j] + 1) for all j < i if nums[j] < nums[i]
例子
nums = [10,9,2,5,3,7,101,18]
→ LIS = [2,3,7,101] 长度=4
典型模型二：股票买卖（最多k次交易）
问题
每天有股票价格，求最大利润。
状态定义
dp[i][k][0/1]：第i天，最多交易k次，是否持有股票。
转移
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + price[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
🧱 四、区间 DP（Interval DP）
定义
状态定义在一个区间 [l, r] 上，通常需要合并区间或划分点。
特征：
- 子问题是“区间”；
- 需要枚举分割点；
- 常见时间复杂度 O(n³)。
典型模型一：矩阵链乘法 / 石子合并
问题
给定 n 堆石子，每次合并相邻两堆，代价为两堆石子总数，求最小总代价。
状态
dp[l][r] = 合并 [l, r] 的最小代价
转移
$$
dp[l][r] = \min_{k=l}^{r-1} (dp[l][k] + dp[k+1][r] + sum(l,r))
$$
典型模型二：戳气球（LeetCode 312）
问题
戳气球使得金币最大。
状态
dp[l][r] = 戳完 (l,r) 之间气球获得的最大金币
转移
枚举最后一个戳的气球 k：
$$
dp[l][r] = \max_{k}(dp[l][k] + dp[k][r] + nums[l]*nums[k]*nums[r])
$$
🎒 五、背包 DP（Knapsack DP）
定义
给定若干“物品”，每个物品有“体积/重量”和“价值”，在容量限制下最大化或最小化目标。
状态
dp[i][w] = 用前 i 个物品、容量 w 能达到的最大价值。
转移
0/1 背包：
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)
完全背包（可重复）：
dp[i][w] = max(dp[i][w-wi] + vi, dp[i-1][w])
例题
- 0/1 背包
- 完全背包
- 多重背包（分组或二进制分解）
- 多维背包（体积+重量）
- 分组背包
🌲 六、树形 DP（Tree DP）
定义
在树结构上进行动态规划，状态依赖于子树的结果。
常见思路：DFS 后序遍历，合并子树结果。
典型模型一：树上选点（最大独立集）
问题
树上每个节点有权值，不能选相邻的节点，求最大权值和。
状态
dp[u][0] = 不选u的最大值 dp[u][1] = 选u的最大值
转移
for child in children[u]: dp[u][0] += max(dp[child][0], dp[child][1]) dp[u][1] += dp[child][0]
典型模型二：树上路径优化 / 换根 DP
- 求树的直径（最大路径）
- 每个节点的子树贡献，换根更新全局（rerooting）
🧮 七、状态压缩 DP（Bitmask DP）
定义
当状态空间与子集有关时，用二进制掩码压缩表示。
典型模型一：旅行商问题（TSP）
问题
n个城市，求访问所有城市的最短路径。
状态
dp[mask][i] = 访问过集合 mask，最后在城市 i 的最短路径。
转移
dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i])
复杂度 O(n²·2ⁿ)
典型模型二：匹配问题 / 分配问题
例如：任务分配，每个人一个任务。
状态 = 哪些任务已分配。
dp[mask] 表示分配前 mask 个任务的最优代价。
🔢 八、数位 DP（Digit DP）
定义
处理与“数位（digit）”有关的计数或统计问题，比如“有多少个数满足条件”。
状态常见定义
dp[pos][tight][property]：
处理到第 pos 位，是否受上界限制 (tight)，属性如数位和、余数、是否含特定位。
典型模型：统计不含 4 或 9 的数字
问题
统计 [1, n] 之间不含 4 的数有多少。
转移
按位枚举当前数字 d：
- 如果 tight = 1，只能枚举到上界；
- 如果 tight = 0，可枚举 0~9；
- 若 d=4 跳过。
数位 DP 通常写成带记忆化的 DFS。
🌉 九、图上 DP（Graph DP / DAG DP）
定义
图是有向无环图 (DAG)，状态依赖于拓扑序。
常见思路
- 拓扑排序后从起点向后推；
- 每个节点 dp[u] = max(dp[v] + weight(u,v)) for all v→u。
典型模型：最长路径 in DAG
例题
给定 DAG，求最长路径长度。
for u in topo_order: for v in graph[u]: dp[v] = max(dp[v], dp[u] + weight[u][v])
🔄 十、区间划分 DP（Partition DP）
有时称作“分段 DP”。
问题类型
给定一段序列，想要分成若干段，每段满足某种性质，求最优。
状态
dp[i] = 前 i 个元素的最优结果。
转移
dp[i] = min/max_{j < i} (dp[j] + cost(j+1, i))
例题
- 切绳子最大乘积
- 单词分割
- 视频剪辑 / 最小子数组划分
🔁 十一、计数 DP（Counting DP）
目标是计算“方案数”，不是最值。
例子
- 爬楼梯：
dp[n] = dp[n-1] + dp[n-2]
- 背包计数：
dp[j] += dp[j - w[i]]
- 矩阵路径计数：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
这类问题常常与组合数学结合。
♟️ 十二、博弈 DP（Game DP）
定义
两人轮流操作，每次决策影响状态，目标是判断谁能赢。
常见思想：后继状态若有一个是必败，则当前必胜。
例题
- NIM 博弈：如果所有堆异或为 0 → 先手必败。
- 石子游戏：
dp[l][r] = max(sum[l,r] - min(dp[l+1][r], dp[l][r-1]))
🧠 十三、记忆化搜索 DP（Top-down DP）
定义
与递推 DP（bottom-up）不同，用递归 + 缓存表实现。
例题
斐波那契数列：
@lru_cache(None) def f(n): if n <= 1: return n return f(n-1) + f(n-2)
优点
- 思路自然；
- 适合复杂状态；
- 调试容易。
缺点
- 递归深；
- 难以控制空间。
📈 十四、概率/期望 DP（Expected DP）
定义
状态表示某个事件的期望或概率。
例题
掷骰子期望次数：
E = 1 + (1/6) * (E + ...)
或者“期望回合数”问题常用：
$$
E[i] = 1 + \sum P(i→j)·E[j]
$$
🧩 十五、其他进阶类型
类别 | 含义 | 示例 |
二维/多维 DP | 多个维度的限制 | 背包+时间、路径+状态 |
滚动数组 DP | 降低空间复杂度 | 背包、路径 |
状态机 DP | 状态有限但转移复杂 | 股票买卖、字符串匹配 |
动态规划 + 前缀优化 | 使用前缀和、单调队列、斜率优化等优化转移 | 最短路径分段、区间加速 |
树形背包 | 树结构 + 背包约束 | 子树选择资源最优 |
🎯 十六、DP 思考模板（统一思维）
当你拿到任何DP题，问自己这5个问题：
步骤 | 问题 | 含义 |
1️⃣ | 状态是什么？ | 子问题怎么定义？ |
2️⃣ | 状态转移方程？ | 当前与前面怎么关联？ |
3️⃣ | 初始化？ | 最小规模的子问题怎么求？ |
4️⃣ | 顺序？ | 从前往后/从后往前？ |
5️⃣ | 答案？ | 要输出哪个 dp 值？ |
🏁 十七、总结大表
类型 | 代表问题 | 状态定义 | 关键思想 |
线性 DP | LIS、股票买卖 | dp[i] | 从前状态转移 |
区间 DP | 石子合并、戳气球 | dp[l][r] | 枚举分割点 |
背包 DP | 0/1、完全、多重背包 | dp[i][w] | 枚举物品与容量 |
树形 DP | 树上独立集 | dp[u][0/1] | DFS合并子树 |
状压 DP | TSP、任务分配 | dp[mask][i] | 位掩码压缩 |
数位 DP | 不含4的数 | dp[pos][tight][sum] | 枚举数位 |
图上 DP | DAG 最长路径 | dp[u] | 拓扑序推导 |
区间划分 DP | 分段最优 | dp[i] | 枚举分割点 j |
计数 DP | 爬楼梯、路径数 | dp[i][j] | 加法转移 |
博弈 DP | 石子游戏 | dp[l][r] | 对手最优反应 |
期望 DP | 掷骰期望 | E[i] | 概率转移方程 |
记忆化 DP | Top-down | dfs(state) | 缓存子问题 |
如果你希望我继续，我可以：
- 📘 给你一份「DP类型 → 模板代码 + 推导公式 + 常见陷阱」的 LaTeX 总结表；
- 或者 📊 给出「每类DP的图解与典型例题」（带图形状态转移说明）。
👉 你想要哪一种？