[L2] 30_动态规划

核心哲学：动态规划是在 DAG 上寻找最优路径。
优化的直觉在于：“剪枝”：排除无效决策。“降维”：压缩重复状态。

1. 知识图谱与演化

• 核心工具: 状态定义、转移方程、决策单调性、状态压缩。

• 演化路径:

  1. 基础模型：线性、背包、区间、树形。解决“怎么定义状态”。

  2. 状态压缩：利用位运算压缩 “开关” 类状态。

  3. 决策优化：利用单调队列、斜率优化降低转移复杂度。

  4. 进阶模型：结合数论、自动机或动态修改。

2. 决策矩阵

• 状态如开关且 $N \le 20$：[[Note] 状压 DP]。

• 转移含 $\min/ \max$ 且前驱可整理为单向窗口：单调队列优化DP模型，含乘积项时再判断 [[Note] 斜率优化]。

• 树上子树合并 / 依赖关系：[[Note] 树形 DP]。

• 计数类 / 字符串匹配统计：[[Note] 计数 DP] 或 [[Note] 自动机 DP]。

3. 核心板块索引

3.1 [L3] [[31_经典模型]]

• 线性DP: LIS, LCS 等。

• 背包DP: 01, 完全, 多重, 分组。

• [[区间DP]]: 合并类问题 (石子合并)。

• 树图DP: 树上背包, 换根 DP.

3.2 [L3] [[32_状态压缩]]

• [[Note] 状压DP]：位运算全排列。

• [[SOSDP]]：子集和 DP (Sum Over Subsets).

3.3 [L3] [[33_决策优化]]

• 单调队列优化DP模型：从窗口合法性与稳定支配关系判断能否压缩转移。

• [[Note] 斜率优化]: 凸包维护最优决策点。

• [[Note] WQS 二分]: 带限制的凸函数优化。

3.4 [L3] [[34_进阶模型]]

• [[Note] 数位 DP]: 按位统计。

• [[Note] 计数 DP]: 组合方案数。

• [[Note] 自动机 DP]: 结合 AC 自动机/SAM。