1树形DP·概念
树形 DP 里 dp[u] 通常表示关于哪一部分的信息？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2树形DP·状态
dp[u][1] 表示什么含义？
3树形DP·转移
选了 u，它的孩子 v 还能选吗（相邻不能同选时）？
4树形DP·例题
最终答案取根结点的哪个值？
5树的直径
经过某点 u 的最长路径，为什么用最长链加次长链？
6换根DP直觉
换根 DP 大约需要几遍 DFS？
7状压DP·概念
二进制 101 表示选了哪几个元素（从第 0 位算起）？
8状压·位运算
写出“判断 S 的第 3 位是否为 1”的表达式。
9状压·TSP直觉
dp[S][i] 的两维分别记录了什么？
10状压·棋盘直觉
状压处理棋盘时，一个状态通常压缩的是多大范围？
第 1 页 · 背面（答案）
参考答案（家长）：在选取 u 的前提下，u 的子树能得到的最优值。
参考答案（家长）：以 u 为根的整棵子树。
参考答案（家长）：max(dp[根][0], dp[根][1])（选或不选根取较大）。
参考答案（家长）：不能，只能取 dp[v][0]。
参考答案（家长）：两遍（一遍自底向上，一遍自顶向下换根）。
参考答案（家长）：一条向左下、一条向右下，两条不同子树的链拼起来最长。
参考答案（家长）：(S>>3)&1（为 1 则该位是 1）。
参考答案（家长）：第 0 位和第 2 位（共两个元素）。
参考答案（家长）：一整行（列数不多）的选取情况。
参考答案（家长）：已访问城市的集合 S，以及当前所在城市 i。
第 2 页 · 正面（题目）
11数位DP·概念
数位 DP 适合解决哪类问题？
12数位DP·状态
为什么“贴着上界”的状态一般不能直接记忆化复用？
13单调队列·概念
单调队列和普通队列相比多了什么操作？
14滑动窗口最值
求窗口“最大值”时，队列里元素应保持递增还是递减？
15单调队列优化DP
单调队列优化把这类 DP 的复杂度从 O(n²) 降到多少？
16多重背包·概念
多重背包和完全背包的区别在哪？
17多重背包·二进制
某物品有 7 件，二进制拆分成几个包？件数各是多少？
18分组背包
分组背包每组最多能选几件物品？
19二维费用背包
二维费用背包的 dp 数组比普通 01 背包多了哪一维？
20背包·求方案数
求方案数时 dp[0] 应初始化为多少？
第 2 页 · 背面（答案）
参考答案（家长）：贴上界时本位取值受限、情形特殊，和自由填的状态不通用。
参考答案（家长）：统计一个大范围内满足某种数位性质的数的个数。
参考答案（家长）：递减（队头最大）。
参考答案（家长）：从队尾弹出不再有用的元素以维持单调。
参考答案（家长）：多重背包每种物品件数有限，完全背包无限。
参考答案（家长）：O(n)。
参考答案（家长）：一件（也可以一件都不选）。
参考答案（家长）：3 个包：1、2、4（可组合出 0~7 任意件数）。
参考答案（家长）：1（凑出容量 0 恰有“空选”这一种方案）。
参考答案（家长）：第二种资源（如体积）的容量维。
第 3 页 · 正面（题目）
21前缀与后缀
字符串 "abab" 最长的相等前后缀（不含它本身）是什么？
22KMP·暴力慢在哪
暴力匹配失配后，模式串会怎么处理已比对的信息？
23KMP·next含义
next[i] 记录的是什么长度？
24KMP·求next
求 next 时若 p[i] 与 p[j] 不相等，j 该怎么变？
25KMP·匹配过程
KMP 匹配时文本指针 i 会回退吗？
26KMP·循环节
"abcabc" 的最小循环节长度是多少？
27Trie·概念
Trie 上从根到某结点的路径代表什么？
28Trie·插入
插入时遇到不存在的字符孩子该怎么办？
29Trie·查询
查完整单词和查前缀，结尾判断有何不同？
30Trie·前缀统计
pass 计数在插入时怎样更新？
第 3 页 · 背面（答案）
参考答案（家长）：全部丢弃，右移一位从头再比（所以慢）。
参考答案（家长）："ab"（前缀 ab = 后缀 ab，长度 2）。
参考答案（家长）：j=next[j]，不断回退直到相等或 j 变为 0。
参考答案（家长）：模式串前 i 个字符中最长相等前后缀的长度。
参考答案（家长）：3（即 6-next[6]=6-3=3，对应 "abc"）。
参考答案（家长）：不会，i 只前进，回退的是模式指针 j。
参考答案（家长）：新建一个结点，再沿它走下去。
参考答案（家长）：一个字符串前缀。
参考答案（家长）：插入路径上经过的每个结点都 pass++。
参考答案（家长）：查单词要看末尾“结束”标记；查前缀只要能走完路径即可。