分类标签归档：dp
DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
+ a：额外产生 a 个新人，该通道原有人数不变。x a：设该通道操作前有 P 人，操作后变为 P·a 人——相当于原有 P 人保持为「基底」，额外新增 (a...数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。
题意：如果一个正整数的各位数字互不相同，就称它为特殊整数；给定正整数 n，统计 $[1, n]$ 中特殊整数的个数。
模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：
i：当前填到第几位；mask：已选数字的集合，避免重复选数；is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；is_num：前面是否已经填过非零数...朴素转移超时，不是 DP 的终点，而是优化的起点。本合集收录「先写对、再打磨复杂度」的 DP 优化技巧题（状态怎么设计的题在《DP 状态设计》里）。
题意：统计长度为 n、每个元素都在 $[l, r]$ 内的数组个数，要求相邻元素不相等，且任意连续三个元素都不构成严格递增或严格递减（即上升、下降交替出现），答案对 $10^9+7$ 取模。$3 \le n \le 2000$，$1 \le l < r \le 2000$。
寻找子问题：如果长度为 i 的序列此刻是「递增收尾」的（第 i 个数大于第 i-1 个数，下标从 1 开始），那它的前...