1什么是DP
说出爬楼梯问题里的“大问题”和“小问题”分别是什么。
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2记忆化搜索
算 f(5) 时（不做记忆化），f(2) 大约被重复计算几次？
3状态与转移
为爬楼梯写出初始值 dp[1] 和 dp[2]。
4爬楼梯回顾
n=5 时 dp[5] 等于多少？
5最大子段和
序列 2 -1 3 的最大子段和是多少？
601背包·问题
容量 5，物品甲（重 3 值 4）、乙（重 2 值 3），两个都拿得下吗？总价值多少？
701背包·状态
dp[0][j]（一个物品都不考虑）应该等于几？
801背包·转移
若当前物品重 3，而容量 j=2，能选它吗？转移取哪一支？
901背包·写全
内层循环从 j=0 开始会不会出错？
10背包·滚动优化
如果内层改成从小到大，会出现什么错误？
第 1 页 · 背面（答案）
参考答案（家长）：约 3 次，正说明需要记忆化。
参考答案（家长）：大问题=到第 n 阶的走法数；小问题=到更低阶（n-1、n-2）的走法数。
参考答案（家长）：dp[3]=3, dp[4]=5, dp[5]=8，答案 8。
参考答案（家长）：dp[1]=1，dp[2]=2。
参考答案（家长）：3+2=5≤5，都能拿，总价值 4+3=7。
参考答案（家长）：dp 依次为 2,1,4，最大是 4（即 2+(-1)+3）。
参考答案（家长）：不能选（2<3），只能 dp[i][j]=dp[i-1][j]。
参考答案（家长）：0（没有物品可选，价值为 0）。
参考答案（家长）：物品会被重复选取，变成了“可重复拿”的完全背包。
参考答案（家长）：不会；j<w[i] 时自动跳过“选”的分支，等于只继承上一行。
第 2 页 · 正面（题目）
11完全背包
01 背包与完全背包在代码上唯一的区别是什么？
12最长上升子序列
序列 1 3 2 4 的最长上升子序列长度是多少？
13LIS·优化
为什么 g[] 里要存“最小的结尾值”，而不是随便一个？
14编辑距离直觉
把 “cat” 变成 “cut” 最少几步？
15区间DP直觉
区间 DP 里 dp[l][r] 的下标 l 和 r 谁大谁小？
16链表概念
数组和链表，哪个能 O(1) 直接访问第 100 个元素？
17链表结点
next 是 nullptr 说明什么？
18指针直觉
写出让指针 p 前进一步的语句。
19插入与删除
插入时若先写 p->next=q 再写 q->next=p->next 会怎样？
20二叉树概念
一个结点最多有几个孩子？最少几个？
第 2 页 · 背面（答案）
参考答案（家长）：3（如 1 3 4 或 1 2 4）。
参考答案（家长）：内层循环方向——01 从大到小，完全从小到大。
参考答案（家长）：1 步（把 a 替换成 u）。
参考答案（家长）：结尾越小，后面越容易接更多数，能保留最大的延伸潜力。
参考答案（家长）：数组（下标直接定位）；链表要从头一个个走过去。
参考答案（家长）：l<=r，l 是左端点、r 是右端点。
参考答案（家长）：p=p->next;
参考答案（家长）：说明这是最后一个结点，后面没有了。
参考答案（家长）：最多 2 个，最少 0 个（叶子）。
参考答案（家长）：q 会指回自己，原来的后续结点全部丢失，链表断裂。
第 3 页 · 正面（题目）
21树的结点
叶子结点的 left 和 right 分别是什么？
22前序遍历
前序遍历第一个访问的一定是哪个结点？
23中序遍历
中序和前序的代码区别在哪一行？
24后序遍历
后序遍历最后一个访问的是哪个结点？
25层序遍历
层序遍历用的是栈还是队列？
26二叉搜索树
BST 中，比根小的数会在根的左边还是右边？
27BST查找
在 BST 里查找时，若 x 大于当前结点值，往哪边走？
28堆的直觉
大根堆的最大值一定在什么位置？
29优先队列用法
默认的 priority_queue<int> 的 top() 取的是最大还是最小？
30哈希表直觉
哈希表理想情况下查找一个元素大约要多少时间？
第 3 页 · 背面（答案）
参考答案（家长）：根结点。
参考答案（家长）：都是 nullptr。
参考答案（家长）：根结点。
参考答案（家长）：输出 r->val 的位置——中序放在两次递归之间。
参考答案（家长）：左边（左小右大）。
参考答案（家长）：队列（先进先出，保证按层顺序）。
参考答案（家长）：堆顶（根）。
参考答案（家长）：往右子树走。
参考答案（家长）：约 O(1)（常数时间）。
参考答案（家长）：最大值（默认大根堆）。