1动态规划回顾
动态规划的三个要素是什么？
考级冲刺 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2状态怎么定
"前 i 个数的最大和"和"以第 i 个结尾的最大和"，哪个好推？
3最大连续和
数组 -2 1 -3 4 -1 2 的最大连续和是多少？
4数字三角形
为什么从下往上推更方便？
5背包问题
每件只能拿一次的叫什么背包？
6背包的方程
什么情况下"拿"这个选项不成立？
7倒着枚举容量
正着枚举变成了什么问题？
8动态规划练习
状态该怎么定？
9搜索还是动态规划
爬楼梯用搜索和用动态规划，差别在哪？
10记忆化搜索
记忆化搜索需要多准备什么？
第 1 页 · 背面（答案）
参考答案（家长）：后者。因为它能明确地由前一个状态推出来。
参考答案（家长）：状态、转移方程、初始值。
参考答案（家长）：不用处理边界，最后答案就在顶点。
参考答案（家长）：5（4 + -1 + 2）。
参考答案（家长）：当前容量装不下这件物品时。
参考答案（家长）：01 背包。
参考答案（家长）：凑出金额 j 所需的最少枚数。
参考答案（家长）：完全背包，即每件可以拿无限次。
参考答案（家长）：一个数组存"这个状态算过没有、结果是多少"。
参考答案（家长）：搜索会重复算同一个楼层很多次，动态规划每层只算一次。
第 2 页 · 正面（题目）
11图是什么
说出两个生活中的图。
12有向和无向
微信好友和微博关注，各是哪种？
13怎么存图
一万个点、两万条边，用哪种？
14图上的搜索
树需要标记吗？
15数连通分量
如果一次搜索就走遍了所有点，说明什么？
16最短路是什么
边权不同时还能用广搜吗？
17树是什么
家谱是不是一棵树？
18二叉树
编号 3 的节点，两个孩子编号是多少？
19三种遍历
把访问根的那句话放在中间，是哪种遍历？
20中序的妙处
这样的树叫什么？
第 2 页 · 背面（答案）
参考答案（家长）：好友是无向，关注是有向。
参考答案（家长）：如城市和公路、网页和链接。
参考答案（家长）：树没有环，不标记也能停；图必须标记。
参考答案（家长）：邻居列表。表格要存一亿个格子，装不下。
参考答案（家长）：不能，要用专门的最短路算法。
参考答案（家长）：整张图是连通的。
参考答案（家长）：6 和 7。
参考答案（家长）：是。每个人只有一个父节点，没有环。
参考答案（家长）：二叉排序树（二叉搜索树）。
参考答案（家长）：中序。
第 3 页 · 正面（题目）
21优先队列
想想哪些场景需要"每次取最小"。
22复杂度再练
广搜遍历整张图是什么复杂度？
23空间也要算
能开一个 10000×10000 的整数二维数组吗？
24从暴力到优化
为什么先写暴力也有价值？
25对拍
对拍需要准备哪三样？
26随机数据生成
为什么对拍时数据要小？
27调试的顺序
把这四步记下来。
28学会看题解
看完题解后，你会做什么？
29分类整理
把最近做的十道题分个类。
30一题多解
挑一道题，用第二种方法再做一遍。
第 3 页 · 背面（答案）
参考答案（家长）：每个点和每条边各处理一次，是 O(点数+边数)。
参考答案（家长）：如每次合并最小的两堆、每次处理最近的点。
参考答案（家长）：能拿部分分，也能用来验证优化后的答案对不对。
参考答案（家长）：不能，那是一亿个数、约 400MB，通常超限。
参考答案（家长）：出错时能手动算出正确答案，方便定位。
参考答案（家长）：待测程序、暴力程序、随机数据生成器。
参考答案（家长）：合上题解自己独立写一遍，写不出来说明还没真懂。
参考答案（家长）：有固定流程，遇到问题就不会慌。
参考答案（家长）：能说出两种方法的优劣，才算真正掌握。
参考答案（家长）：分类后会发现，很多题其实是同一个套路换皮。