1区间 DP 的循环顺序
为什么要按长度从小到大？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2合并石子
区间和怎么快速算？
3环形区间 DP
为什么复制一份就能处理环？
4最长回文子串
长度为 1 和 2 的区间怎么处理？
5数位 DP 是什么
什么样的题会用数位 DP？
6数位 DP 的关键
为什么要记这个？
7状压 DP 回顾
n 是 20，状态有多少个？
8状压 DP：旅行商
这个状态有多少个？
9状压 DP：棋盘
为什么只需记上一行？
10树形 DP 回顾
树形 DP 的递归顺序是什么？
第 1 页 · 背面（答案）
参考答案（家长）：用前缀和。
参考答案（家长）：大区间要用小区间的结果，小的必须先算好。
参考答案（家长）：长度 1 一定是回文，长度 2 看两个字符是否相同。
参考答案（家长）：环上任意一段，在复制后的数组里都是连续的一段。
参考答案（家长）：否则不知道当前位能填到几，会算错。
参考答案（家长）：如统计 1 到 n 中含数字 7 的数有多少个。
参考答案（家长）：2 的 n 次方乘以 n。
参考答案（家长）：约一百万个，可以接受。
参考答案（家长）：先递归所有孩子，回来再合并。
参考答案（家长）：如果限制只涉及相邻行，更早的行就不影响了。
第 2 页 · 正面（题目）
11树上背包
这比普通背包多了什么？
12换根 DP
这能省多少？
13概率与期望 DP
为什么期望 DP 常常倒着推？
14滚动数组
01 背包一维写法用的是这个吗？
15一千五百天
回头看看第一年的纸条。
16单调队列
为什么可以把不可能成为答案的元素直接扔掉？
17单调队列优化 DP
这能把复杂度从多少降到多少？
18单调栈
柱状图最大矩形用的是它吗？
19前缀和优化 DP
这和单调队列优化是一个思路吗？
20矩阵快速幂
斐波那契第 10 亿项能这样求吗？
第 2 页 · 背面（答案）
参考答案（家长）：从 n 次遍历降到两次。
参考答案（家长）：多了"容量在孩子之间怎么分"这一层枚举。
参考答案（家长）：正是，把二维压成了一维。
参考答案（家长）：终止状态的期望已知（通常为 0），从它往回推最自然。
参考答案（家长）：它既比新来的小又比新来的早出窗口，永远轮不到它。
参考答案（家长）：会发现当初的难题现在只是常识。
参考答案（家长）：是，找每根柱子左右第一个更矮的位置。
参考答案（家长）：从 n 平方降到 n。
参考答案（家长）：能，约 30 次矩阵乘法。
参考答案（家长）：思路一致 —— 都是把转移里的重复计算提前算好。
第 3 页 · 正面（题目）
21DP 练习一
该用哪种做法？
22DP 练习二
这是哪种背包？
23DP 练习三
这是哪类 DP？
24DP 练习四
状态怎么定？
25DP 调试方法
为什么打印 dp 数组比看代码有效？
26DP 常见错误
把这四条记下来。
27从暴力到 DP
为什么先写搜索？
28记忆化搜索的好处
记忆化搜索的缺点是什么？
29字符串：暴力匹配
什么情况下暴力匹配最慢？
30KMP 的思想
这个"能跳多少"由什么决定？
第 3 页 · 背面（答案）
参考答案（家长）：完全背包，容量正序枚举。
参考答案（家长）：n log n 的二分做法，平方做法会超时。
参考答案（家长）：每个点选与不选两个状态。
参考答案（家长）：区间 DP，按长度从小到大算。
参考答案（家长）：写完对照检查一遍。
参考答案（家长）：能直接定位到第一个出错的状态。
参考答案（家长）：递归开销大，深度太大可能爆栈。
参考答案（家长）：搜索好想好写，能验证思路对不对，也能当对拍的标准答案。
参考答案（家长）：由模式串自身的前后缀重合长度决定。
参考答案（家长）：大量部分匹配后才失败，如全是同一个字符。