动态规划分类

🧭 动态规划的主要类型分类

动态规划（Dynamic Programming, DP）根据状态结构与转移关系的不同，大致可以分为以下几类👇

---

① 线性 DP（Linear DP）

特点： 状态按顺序递推，每个状态只依赖前面若干个状态。

典型特征： 单一序列、时间线、数量线性推进。

例题：

• 买包子问题
• 股票买卖的最佳时机
• 打家劫舍
• 最长上升子序列（LIS）

---

② 区间 DP（Interval DP）

特点： 状态表示一个区间 [l, r] 的最优值，转移时通过枚举分割点 k 来合并子区间。

典型特征： “区间划分”“合并”“括号匹配”“矩阵连乘” 类问题。

例题：

• 矩阵链乘（Matrix Chain Multiplication）
• 括号匹配问题
• 石子合并 / 文件合并
• 最优二叉搜索树

---

③ 二维 DP（Two-dimensional DP）

特点： 状态由两个序列或两个维度构成，例如 (i, j)。

典型特征： 双序列匹配、编辑距离、网格路径问题。

例题：

• 最长公共子序列（LCS）
• 编辑距离（Edit Distance）
• 网格最短路径（走格子问题）

---

④ 背包 DP（Knapsack DP）

特点： 核心是“取与不取”，状态通常是 (物品, 容量) 二维结构。

典型特征： 优化选取组合，在约束条件下求最大/最小值。

例题：

• 0-1 背包问题
• 完全背包 / 多重背包
• 组合总和类问题

---

⑤ 树形 DP（Tree DP）

特点： 状态依赖于树的结构，从子节点向父节点递推。

典型特征： “子树合并”“选或不选”“父子依赖”。

例题：

• 树的最大独立集
• 树的路径权值和
• 树形背包

---

⑥ 状压 DP（State Compression DP）

特点： 用二进制（bitmask）表示状态集合，通过位运算转移。

典型特征： 状态数较小（一般 ≤ 2¹⁶），用于排列组合、子集类问题。

例题：

• 旅行商问题（TSP）
• 集合覆盖问题
• 棋盘放置问题

---

⑦ 数位 DP（Digit DP）

特点： 在按位枚举数字时，用 DP 记录前缀状态（如是否受限、某种属性）。

典型特征： 与数字构造、计数相关。

例题：

• 统计区间内满足条件的数（如不含4的数）
• 统计某种数字出现次数

---

⑧ 概率 / 期望 DP（Probabilistic / Expected DP）

特点： DP 中保存的是概率或期望值，而非确定值。

典型特征： 涉及随机事件、博弈、期望步数问题。

例题：

• 扔骰子期望次数
• 猜数游戏期望步数
• 博弈胜率计算

---

⑨ 记忆化搜索型 DP（Top-down DP）

特点： 递归 + 记忆化方式实现的 DP，本质仍是DP，只是计算顺序不同。

例题：

• 路径搜索类问题
• 剪枝优化的区间/树形DP

---

⑩ 其他特殊类型（拓展）

可结合图论、贪心、数学优化形成：

• 图上DP（如最短路DP、拓扑DP）
• 滚动数组DP（空间优化）
• 分层DP / 多维DP（状态扩展）

---

✅ 小结表格

类型	状态结构	应用场景	难度等级
线性DP	一维顺序	序列最优、时间线	⭐
二维DP	双序列	编辑距离、LCS	⭐⭐
区间DP	区间划分	石子合并、矩阵连乘	⭐⭐⭐
背包DP	二维（物品×容量）	选取优化	⭐⭐
树形DP	树结构	子树合并	⭐⭐⭐
状压DP	二进制状态	组合搜索	⭐⭐⭐⭐
数位DP	位状态	数字计数	⭐⭐⭐
概率DP	概率/期望	博弈、期望问题	⭐⭐⭐
图上DP	拓扑/路径	DAG优化问题	⭐⭐