状态定义与递推方向设计一类题的合集（区别于《优化DP》的复杂度优化技巧类），随训练持续更新。
https://codeforces.com/problemset/problem/2078/D
有 n 对门，每对门都有左、右两个通道。初始时，左右通道各有一个人，并且这些人不能中途切换通道。
当我们通过第 i 对门的某个具体门（左或右）时：
* 如果是加法门 (+ a)：会额外产生 a 个新的人。该通道内原先存在的人数不变。
* 如果是乘法门 (x a)：假设该通道在操作前有 P 个人，操作后会
图论一类题的合集，随训练持续更新。
题意：从起点按序输出唯一路径
python写一直re，后面发现需要使用sys.setrecursionlimit(int(2 * 10**5))扩大python默认递归深度限制，以达到题目要求
邻接表建图用字典的setdefault方法初始化空列表最简洁
import sys
sys.setrecursionlimit(int(2 * 10**5))
n = int(input())
vised = {}
graph = {}
in_degree = {}
for _ in ra线段树一类题的合集，随训练持续更新。
用python重写下线段树模板，线段树的记忆点在于脑子里要有线段树，特点是自顶向下构建
class segment_tree:
def __init__(self, nums):
n = len(nums)
self.nums = nums
self.tree = [0] * 4 * n
self.tag = [0] * 4 * n
def update(self, root):
self.tree[rleetcode 208
模板，注意别忘了is_end表示单词结束
leetcode 648
对每个单词找最短前缀，特点是遇到is_end就停
leetcode 1233
要求输出所有最顶级的父文件夹。需要特判'/'的位置，前缀匹配到不一定都是父文件夹，下一位是'/'的才是。
leetcode 1268
可以构建字典树后枚举前缀dfs找前三个单词，dfs的复杂度取决于products[i]的长度，3000*1000规模可以过；
这里一个优化是先把products排序，这样插入是按字母序插入，可以在前面就把推荐数组预存下来，这样在字典树上遍历searchWord时可以O(1)获得答
leetcode 1006
逆波兰表达式需要维护数字和操作符两个栈，这题由于操作符顺序是固定的，可以不用操作符栈。
题目乘法和除法是连在一起算的，加法是单独算的，减法减去的值总是乘除的结果，模拟一下即可。
需要注意除法的负数取值。
leetcode 394
可以dfs也可以用栈迭代模拟，新学了这种dfs的方法叫递归下降解析，“下降”指的是我们从最高层级，一层层往下去匹配，是用来处理嵌套解析的一种方式。
特点是维护全局index，相比每次都去搜索匹配右括号（O(n^2)），这种全局index扫描的方法因为每个字符只被处理一次，所以保证了O(n)的线性时间复杂度，效率最高。
注意如
leetcode 523
题意：问是否存在子数组（长度大于1）的和能被k整除。
前缀和的经典问题，务必掌握。
子数组的和可以表示为两个前缀和相减的形式，看到整除第一反应应该是对k求余余数为0，因此推出两个前缀和关于k同余。
把前面的前缀和对k对余数加入哈希表，遍历前缀和的时候O(1)查找
平方剩余核 core(n) 为 n 除去完全平方因子后的剩余结果。
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
leetcode 3715
问题转化：两个数x, y相乘要想是完全平方数 => core(x) == core(y)
接着把树转成一个无向图dfs即可，注意搜索顺序，只
leetcode 2376
模板题，用记忆化搜索实现会更加直观，需要知道的信息有：
1. 当前到第几位
2. 已选集合，避免重复
3. 是否到上限，到不到上限在同一位上可选范围是不一样的
4. 是否开始计数（考虑前导0）
class Solution:
def countSpecialNumbers(self, n: int) -> int:
s = str(n)
@cache
def dfs(i, mask, is_limit, is_num):
if i == len(s):
leetcode 3699
寻找子问题：如果长度为n的序列此时是递增的，它的前一个状态必须是递减的且位置n(index从1开始)的数必须大于位置为n-1的数。这时我们发现需要两个维度和两个数组定义状态，一个维度表示当前序列长度i，另一个维度表示当前结尾的数字j。一个数组dp1表示当前状态是递增时的方案数，另一个数组dp2表示当前状态是递减时的方案数。两个数组的计算方式完全对称。为简化计算，[l, r]区间可以对应到[0, r - l]。
dp1[i][j] = dp2[i - 1][0] + dp2[i - 1][1] + ... + dp2[i - 2][j - 1