下面给出动态规划（DP）中最经典的问题类型与对应的典型状态定义（State Definition）大全，按主题系统归纳，方便学习与复习。每类均附带问题特征、常用状态表示、典型转移。
一、序列型 DP（Sequence DP）
1. 最长上升子序列（LIS）
状态定义：
( dp[i] )：以第 (i) 个元素结尾的 LIS 长度
转移：
若 (a[j] < a[i])，则
( dp[i] = \max(dp[i], dp[j] + 1) )
2. 最长公共子序列（LCS）
状态定义：
( dp[i][j] )：A 的前 (i) 个与 B 的前 (j) 个的 LCS 长度
转移：
- 若相等：( dp[i][j] = dp[i-1][j-1] + 1 )
- 否则：取最大
3. 最长公共子串
状态定义：
( dp[i][j] )：以 A[i] 与 B[j] 结尾的最长公共子串长度
转移：
相等 → 继承；否则为 0
4. 编辑距离 / Levenshtein Distance
状态定义：
( dp[i][j] )：将 A 的前 i 个变为 B 的前 j 个的最少操作数
转移：
插入 / 删除 / 替换三类操作取最小
5. 最大子段和 / 最大子数组和（Kadane）
状态定义：
( dp[i] )：以 i 结尾的最大子段和
转移：
( dp[i] = \max(dp[i-1] + a[i], a[i]) )
二、背包型 DP（Knapsack DP）
1. 0-1 背包
状态定义：
( dp[i][j] )：前 i 件物品、容量 j 的最大价值
或一维优化：( dp[j] )
2. 完全背包
状态定义：
同 0-1 背包
转移区别：
完全背包内层 j 正序遍历
3. 多重背包
状态定义：
同上，但对单件物品有限次
方法： 分组、二进制优化
4. 组合类：零钱兑换、划分等
状态定义：
( dp[x] )：金额 x 的方案数
转移：
对硬币 c：
( dp[x] += dp[x-c] )
三、区间 DP（Interval DP）
适用于“合并、分裂、括号、区间取值”等问题。
1. 石子合并
状态定义：
( dp[l][r] )：合并区间 [l, r] 的最小代价
转移：
在 k 上切分
( dp[l][r] = \min(dp[l][k] + dp[k+1][r] + sum(l,r)) )
2. 戳气球 / 区间分裂型
状态定义：
( dp[l][r] )：戳掉区间 (l, r) 的最大得分
转移：
枚举最后戳掉的气球 k
3. 最优二叉搜索树（Optimal BST）
状态定义：
( dp[l][r] )：构造 [l,r] 作为子树的最小期望代价
四、树形 DP（Tree DP）
1. 树的最大独立集
状态定义：
( dp[u][0/1] )：节点 u 不选/选 时子树能取得的最大值
转移：
若 u 被选，子节点不得选
2. 树的直径（DP 版本）
状态定义：
( dp[u] )：从 u 向下的最长链
转移：
取子树最大两个链之和更新答案
3. 树的重心、子树大小
状态定义：
( size[u] )：子树大小
( dp[u] )：某种全局量（如距离和）
五、状态压缩 DP（Bitmask DP）
1. 旅行商问题（TSP）
状态定义：
( dp[S][i] )：集合 S 中的点已访问，当前在 i 的最小路径
转移：
枚举下一个点
2. 分组匹配 / 最小权完美匹配（G-match）
状态定义：
( dp[mask] )：mask 表示哪些点已匹配
3. N 皇后计数（通常优化）
状态定义：
使用 bitmask 表示列 / 对角线
六、图 DP（DAG DP）
1. 有向无环图上的最长/最短路径
状态定义：
( dp[u] )：从起点到 u 的最优值
特征：
在拓扑序上转移
2. 计数路径
状态定义：
( dp[u] )：到 u 的方案数
七、数位 DP（Digit DP）
1. 统计区间内满足某条件的数字数量
状态定义：
( dp[pos][state][limit][leadingzero] )
典型状态包括：
- pos：当前处理的位
- state：题目特定状态（如前缀数位和、是否出现过某模式）
- limit：是否受上界约束
- leadingzero：前导零处理
八、概率 DP（Probability DP）
1. 期望步数、随机游走
状态定义：
( dp[i] )：到达目标的期望步数 / 成功概率
2. 期望分数 / 赌徒破产问题
状态定义：
多为
( dp[i] = ... )
满足线性方程组
九、矩阵 DP / 网格 DP
1. 最小路径和（Grid Path）
状态定义：
( dp[i][j] )：走到 (i,j) 的最小代价
2. 独立点数、放置棋子
状态定义：
常配合状态压缩：
( dp[row][mask] )
3. 最大正方形 / 最长连续 1
状态定义：
( dp[i][j] = ) 以 (i,j) 为右下角的最大正方形边长
十、博弈 DP（Game DP）
1. 区间取石子、双方最优
状态定义：
( dp[l][r] )：当前玩家在区间 [l,r] 能获得的最大收益差
（或定义为双方分别的最大收益）
2. Grundy 数 / SG 函数
状态定义：
( sg[x] = mex({sg[y]}) )
十一、集合划分 DP（Partition DP）
1. 划分数组为 K 段的最小代价
状态定义：
( dp[i][k] )：前 i 个元素分成 k 段的最小代价
十二、计数类 DP
1. 组合计数（分组、子序列、子集数）
典型定义：
( dp[n][k] )：使用前 n 个元素选 k 个的方案
( dp[mask] )：子集方案数
十三、字符串结构 DP（Pattern DP）
1. 正则匹配、通配符
状态定义：
( dp[i][j] )：s 前 i 与 p 前 j 是否匹配
2. 回文子序列 / 子串
状态定义：
( dp[l][r] )：区间是否是回文 / 最长回文长度 / 最少删除次数
十四、综合类：常见模板总结
常用状态类型可高度抽象为：
| 类别 | 常用状态 |
|---|---|
| 序列 | dp[i], dp[i][j] |
| 区间 | dp[l][r] |
| 背包 | dp[j], dp[i][j] |
| 树 | dp[u], dp[u][0/1], dp[u][mask] |
| 位压缩 | dp[mask], dp[mask][i] |
| 数位 | dp[pos][state][limit][lz] |
| DAG | dp[u] |
| 网格 | dp[i][j] |
| 博弈 | dp[l][r], sg[x] |