算法进阶 · 小纸条

说出爬楼梯问题里的“大问题”和“小问题”分别是什么。

算 f(5) 时（不做记忆化），f(2) 大约被重复计算几次？

为爬楼梯写出初始值 dp[1] 和 dp[2]。

n=5 时 dp[5] 等于多少？

序列 2 -1 3 的最大子段和是多少？

容量 5，物品甲（重 3 值 4）、乙（重 2 值 3），两个都拿得下吗？总价值多少？

dp[0][j]（一个物品都不考虑）应该等于几？

若当前物品重 3，而容量 j=2，能选它吗？转移取哪一支？

内层循环从 j=0 开始会不会出错？

如果内层改成从小到大，会出现什么错误？

01 背包与完全背包在代码上唯一的区别是什么？

序列 1 3 2 4 的最长上升子序列长度是多少？

为什么 g[] 里要存“最小的结尾值”，而不是随便一个？

把 “cat” 变成 “cut” 最少几步？

区间 DP 里 dp[l][r] 的下标 l 和 r 谁大谁小？

数组和链表，哪个能 O(1) 直接访问第 100 个元素？

next 是 nullptr 说明什么？

写出让指针 p 前进一步的语句。

插入时若先写 p->next=q 再写 q->next=p->next 会怎样？

一个结点最多有几个孩子？最少几个？

叶子结点的 left 和 right 分别是什么？

前序遍历第一个访问的一定是哪个结点？

中序和前序的代码区别在哪一行？

后序遍历最后一个访问的是哪个结点？

层序遍历用的是栈还是队列？

BST 中，比根小的数会在根的左边还是右边？

在 BST 里查找时，若 x 大于当前结点值，往哪边走？

大根堆的最大值一定在什么位置？

默认的 priority_queue<int> 的 top() 取的是最大还是最小？

哈希表理想情况下查找一个元素大约要多少时间？