分类标签归档：dp
DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
https://codeforces.com/problemset/problem/2078/D
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
+ a：额外产生 a 个新人，该通道原有人数不变。x a：设该通道操作前有 P...数位 DP 是「统计 $[1, n]$ 内满足某性质的数字个数」这类题的专用咏唱，模板一旦焊死，剩下的只是换性质。本合集收录数位 DP 题目。
模板题。用记忆化搜索实现比递推直观得多，状态需要携带四样信息：
i：当前填到第几位；mask：已选数字的集合，避免重复选数；is_limit：前面是否一直顶着上界在填——顶着上界时，当前位的可选范围受 n 对应位限制，否则 0 到 9 随便填；is_num：是否已经开始计数，用来处理前导零。class Solution:
def countSpecialNumbers(self, n...朴素转移超时，不是 DP 的终点，而是优化的起点。本合集收录「先写对、再打磨复杂度」的 DP 优化技巧题（状态怎么设计的题在《DP 状态设计》里）。
寻找子问题：如果长度为 n 的序列此刻是「递增收尾」的，那它的前一个状态必须是「递减收尾」的，且第 n 个数（index 从 1 开始）大于第 n-1 个数。于是状态需要两个维度、两个数组：维度 i 表示当前序列长度，维度 j 表示当前结尾的数字；dp1 表示以递增收尾的方案数，dp2 表示以递减收尾的方案数，两者的转移完全对称。为简化计算，把值域 $[l, r]$ 平移到 $[0, r-l...