DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
https://codeforces.com/problemset/problem/2078/D
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
+ a：额外产生 a 个新人，该通道原有人数不变。x a：设该通道操作前有 P...图论一类题的合集，随训练持续补完。用 Python 打 CF，除了算法本身，还得和语言特性过几招——这类实战经验也一并记录在此。
题意：给出无序的边集，它们构成一条链，从端点按序输出这条唯一路径。
思路本身朴素：度为 1 的点是端点，从任一端点 dfs 走到底即可。这题真正的收获是两条 Python 实战经验：
sys.setrecursionlimit(int(2 * 10**5)...数据结构里的高达：拼装麻烦，但拼好之后区间问题基本横着走。本合集收录线段树题目，随训练持续补完。
用 Python 重写的线段树模板。线段树的记忆点在于写代码时脑子里要有那棵树——自顶向下构建，节点 root 的左右孩子是 2*root 和 2*root+1，懒标记在下探时才向下推。
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 ...字典树（Trie）是前缀匹配的专用兵装：把一堆字符串挂在同一棵树上，前缀问题就变成了从根往下走的问题。本合集收录字典树题目。
模板题。唯一容易漏的点：节点上要挂 is_end 标记单词结束，否则「前缀存在」和「单词存在」区分不开。
对每个单词找最短的词根前缀。沿树下行，一碰到 is_end 就停——最先命中的就是最短前缀。
要求输出所有最顶级的父文件夹。坑在 / 的特判：前缀匹配上不代表就是父文件夹，/a/b 是 /a 的子文件夹，但 /ab 不是——匹配结束后下一位是 / 的才算。
表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。
逆波兰一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈。乘除是连着算的，加法单独算，减法减的总是一段乘除的结果，按此模拟即可。需要注意负数除法的取整方向。
可以用栈迭代模拟，也可以 dfs。这里新学了一个名词：这种 dfs 叫递归下降解析——「下降」指从最高层级一层层往下匹配，是处理嵌套结构的标准方式。
它的特点是维护一个全局 index 扫描字符串。相比每次去搜索匹配的右括号（$O(n...
前缀和的核心式只有一条：子数组和可以写成两个前缀和之差，$\text{sum}(i, j) = s_j - s_{i-1}$。围绕这条式子做变形，就是本合集的全部内容。
题意：是否存在长度大于 1 的子数组，其和能被 k 整除。
前缀和的经典问题，务必掌握。子数组和写成 $s_j - s_i$ 后，「和能被 k 整除」即 $s_j - s_i \equiv 0 \pmod k$，移项立刻得到关键结论：两个前缀和关于 k 同余。
于是一遍扫描：把出现过的前缀和对 k 的余数塞进哈希表，扫到每个新前缀和时 $O(1)$ 查同余的旧前缀和是否存...
双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。
同向双指针的一种特殊形态，可以省掉一个显式指针。
数组会被切成若干组，每一组的处理逻辑相同。
外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。
n = len(nums)
i = 0
while i < n:
start = i
while i < n and ...:
i += 1
# 从 star...数论小道具一件：把每个数的平方因子全部剥掉，剩下的「核」才是判断乘积是否为完全平方数的本体。
平方剩余核 core(n)（square-free core）：n 除去所有完全平方因子后剩下的部分。
线性筛的写法，一次预处理出值域内所有数的 core：
MX = 100_001
core = [0] * MX
for i in range(1, MX):
if core[i] == 0:
for j in range(1, isqrt(MX // i) + 1):
core[i * j * j] = i
外层扫到的...
数位 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...