第 12 章 · 动态规划进阶

入门篇学会「设计一个一维状态」后，本章把 DP 的状态维度和技巧全面升级：区间、树形、状压，以及最经典的两序列问题。

学习目标

• 掌握线性 DP 的进阶：最长上升子序列（LIS）、最长公共子序列（LCS）
• 理解区间 DP 的「小区间 → 大区间」合并思想（石子合并）
• 理解树形 DP：在树上定义状态、自底向上转移
• 了解状压 DP：用二进制表示集合状态
• 会做常见的 DP 优化（前缀和优化等）

课程规划（编写中）

• LIS 与 LCS
• 区间 DP
• 树形 DP
• 状压 DP
• DP 优化初步

和搜索的关系

树形 DP 本质是 DFS 上的 DP；状压 DP 常和枚举子集配合。本章会不断回扣第 7 章的搜索。