把 DP 变成看得见的推演

从状态定义到模型迁移，用可改值演示和手算过程建立直觉。

从背包 DP 开始
先读方法论

七种状态空间

37 门课程沿七个 DP 家族展开，从状态含义进入，沿转移路径抵达答案。

滚动或左右拖动浏览
  1. 9 个类型

    背包 DP

    容量受限下的取舍：物品件数属性决定了背包的谱系。从此开始
  2. 7 个类型

    线性 DP

    把问题排成一条推进的序列，dp[i] 只依赖更早的状态。从此开始
  3. 5 个类型

    区间 DP

    dp[l][r] 表示区间最优，枚举分割/合并点，按长度递推。从此开始
  4. 2 个类型

    矩阵 DP

    两条主线：网格坐标上的 DP，与矩阵快速幂加速的递推。从此开始
  5. 4 个类型

    换根 DP

    二次扫描：固定根一遍 DFS，再一遍换根 O(1) 推每个点。从此开始
  6. 5 个类型

    树形 DP

    dp[u][…] 表示子树最优，后序遍历自底向上合并。从此开始
  7. 5 个类型

    状压 DP

    状态是一个集合，用二进制整数表示；转移在 mask 间进行。从此开始

已进入 DP大师 · DP Master