本文整理了从 CSP-J 基础 DP 到 NOI 国集级别所需的全部动态规划技巧。
一、线性 DP
- 最长上升子序列（LIS）：O(n²) 和 O(n log n) 两种做法
- 最长公共子序列（LCS）
- 最大子段和（Kadane 算法）
- 编辑距离（字符串 DP）
二、背包 DP
- 01背包（逆序枚举）
- 完全背包（正序枚举）
- 多重背包（二进制拆分优化）
- 分组背包
- 二维费用背包
- 依赖背包（树形背包基础）
三、区间 DP
- 石子合并问题
- 矩阵链乘
- 括号序列 DP
- 回文串相关 DP
四、树形 DP
- 树的重心
- 树的直径
- 最大独立集
- 树上背包（选课问题）
- 换根 DP（二次扫描）
五、状态压缩 DP
- TSP（旅行商问题）
- 轮廓线 DP
- 插头 DP（高级）
六、其他重要 DP
- 数位 DP
- 概率/期望 DP
- 斜率优化 DP
- 决策单调性优化
- 四边形不等式优化
每种 DP 配有一道经典例题和完整代码模板。建议按顺序学习，每学完一种类型刷 3-5 道练习题巩固。
暂无评论，快来抢沙发吧~ 🛋️