算法进阶 · 小纸条

树形 DP 里 dp[u] 通常表示关于哪一部分的信息？

dp[u][1] 表示什么含义？

选了 u，它的孩子 v 还能选吗（相邻不能同选时）？

最终答案取根结点的哪个值？

经过某点 u 的最长路径，为什么用最长链加次长链？

换根 DP 大约需要几遍 DFS？

二进制 101 表示选了哪几个元素（从第 0 位算起）？

写出“判断 S 的第 3 位是否为 1”的表达式。

dp[S][i] 的两维分别记录了什么？

状压处理棋盘时，一个状态通常压缩的是多大范围？

数位 DP 适合解决哪类问题？

为什么“贴着上界”的状态一般不能直接记忆化复用？

单调队列和普通队列相比多了什么操作？

求窗口“最大值”时，队列里元素应保持递增还是递减？

单调队列优化把这类 DP 的复杂度从 O(n²) 降到多少？

多重背包和完全背包的区别在哪？

某物品有 7 件，二进制拆分成几个包？件数各是多少？

分组背包每组最多能选几件物品？

二维费用背包的 dp 数组比普通 01 背包多了哪一维？

求方案数时 dp[0] 应初始化为多少？

字符串 "abab" 最长的相等前后缀（不含它本身）是什么？

暴力匹配失配后，模式串会怎么处理已比对的信息？

next[i] 记录的是什么长度？

求 next 时若 p[i] 与 p[j] 不相等，j 该怎么变？

KMP 匹配时文本指针 i 会回退吗？

"abcabc" 的最小循环节长度是多少？

Trie 上从根到某结点的路径代表什么？

插入时遇到不存在的字符孩子该怎么办？

查完整单词和查前缀，结尾判断有何不同？

pass 计数在插入时怎样更新？