g6-07070. 记忆化·备忘录提速账 未做

小雅给爬楼梯的递归配上「备忘录」：进函数先查贴纸，算过的直接揭下答案；没算过才算，算完贴一张新的。用上备忘录之后，计算 $f(n)$ 的总时间大约是（ ）。

• A. $O(n)$——状态只有 $n$ 个，每个只算一次，每次转移 $O(1)$，总时间 = 状态数 × 转移代价
• B. $O(2^n)$——搜索树还是原来那棵，一个节点都没少
• C. $O(n^2)$——每个状态都要和前面所有状态比较一遍
• D. $O(\log n)$——查贴纸是折半查找，每次对半砍