DP 入门

复习用，仅记录我知道的方法，个人的见识很少，理解很浅。分类参考《dp 题方法总汇》。

生成结构

集合（背包）

无序。

• 以任意顺序转移，依次确定每个数的系数。

排列

有序，且性质优秀。

两种题：统计排列，统计映射（位置分配）。

排列即位置与值的二分图完美匹配：

• 将匹配拆为先后两部分，按权值依次一起处理左右部点，记录已匹配的对数：P14364 [CSP-S 2025] 员工招聘、CF285E Positions in Permutations。
• 按左部点/右部点（排列/逆排列）顺序依次添加匹配：
  • 考虑已匹配的另一部点的相对顺序：
    • 依左部点（位置）：AT_dp_t Permutation）。
    • 依右部点（数值）：排列逆序对 DP、连续段 DP。
  • 考虑另一部点的绝对大小（通常依赖单调性）：
    • 依左部点：只填一个单调子序列，剩下的组合计数解决；又如 CF1437F Emotional Fishermen。
    • 依右部点：构建笛卡尔树的区间 DP（分成子问题后右部点看相对顺序，归并修正贡献）。

序列

有序，比排列更复杂。

二分图视角：一个左部点恰匹配一个右部点，一个右部点可匹配多个左部点。

防止算重：

• 重排类问题，先对映射计数，再除以阶乘：AT_abc431_f [ABC431F] Almost Sorted 2。
• 对相同数值一起转移。

其他和排列类似。一些特殊序列的常用方法：

括号序列

栈、树等结构都可以视作括号序列。

• 从左到右填，记录未匹配的左括号数：CF1153F Serval and Bonus Problem。
• 状态表示 \((\ldots)\)，有拼接和围括号两种转移：2025.9.25 T4。
• 折线图。

字符串

可以视作自动机上的路径。

• 从前往后或从后往前一位位填，构建一个自动机状态记录关键信息：AT_agc046_d [AGC046D] Secret Passage。

数

统计范围：\([1,x]\) 中的所有数，\(x\) 在 \(y\) 进制下有 \(n\) 位。

本质是带“数的范围”限制的字符串，所以给自动机加状态即可。

• 从高位到低位填：记录是否顶上限、是否已有非 \(0\) 位。
• 从一段区间的两端扩展：先钦定匹配的是哪一段，