爬楼梯：同一道小题会被问两次
到第 n 级只能从 n-1 迈 1 或从 n-2 迈 2。f(5) 要问 f(3) 两次，答案却是同一个 3——记住它，后面只做加法。
dp[i] = 到达第 i 级的方法数。最后一步要么从 i-1 迈 1 级、要么从 i-2 迈 2 级，故 dp[i] = dp[i-1] + dp[i-2]。滚动两个变量即可 O(1) 空间。时间 O(n)，空间 O(1)。
你正在爬一座有 n 阶的楼梯，每次只能爬 1 阶或 2 阶，问有多少种不同的方法能爬到第 n 阶。问的是方法数，不是最短步数；顺序不同算不同方法。
主例 n = 5，答案是 8。八种走法可以逐条写出来：1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、2+1+1+1、1+2+2、2+1+2、2+2+1。再记两个锚点：n=1 只有一种，n=2 有两种（1+1 或 2）。
公式 f(n)=f(n-1)+f(n-2) 不难想到。本文要回答的是：为什么直接递归会把同一道小题算很多遍，以及怎样从 1、2 往上加，把 f(3)=3 只算一次、读两次，得到 8。
最后一步只有两种来源，同一问不要算第二遍
走到第 5 阶的最后一步，只可能从第 4 阶跨 1 阶，或从第 3 阶跨 2 阶。没有第三种来源。于是走到 5 的方法数 = 走到 4 的方法数 + 走到 3 的方法数。把八种走法按最后一步切开：最后一步是 1 的有 5 种，对应已经走到第 4 阶的全部走法再接一个 1；最后一步是 2 的有 3 种，对应第 3 阶的 1+1+1、1+2、2+1 再接一个 2。5+3=8，一种不漏，一种不重。
公式对，但直接递归会把同一问再算很多遍。把 f(5) 的调用树摊开：左边是 f(4)，右边是 f(3)；f(4) 自己又要问 f(3) 和 f(2)。于是 f(3) 出现了 2 次，f(2) 出现了 3 次。两次 f(3) 走进的是同一道题：都是 f(2)+f(1)=2+1=3。左边那棵算完已经知道答案，右边却把整棵子树再长一遍。这就是重叠子问题——同一道更小的题会被反复问到，答案却不变。
分治也拆问题，但切开的两半互不借用中间结果。归并排序左边排完不需要右边的任何数。爬楼梯正好相反：f(4) 和 f(3) 都要 f(2)，它们不独立。因为重叠，才值得把答案存下来；不存，递归树按斐波那契的速度爆炸。暴力递归不是算错了，是拒绝记忆。
有了「大答案由两个小整数完全决定」这一句，状态和转移自己出现。dp[i] 表示到达第 i 级的方法数。边界 dp[1]=1、dp[2]=2。对任意 i≥3：dp[i]=dp[i-1]+dp[i-2]。你不需要知道那 5 种和 3 种走法长什么样，只需要两个整数。少了其中一个，8 这个数拼不出来。
用手从边界往上加。dp[1]=1，dp[2]=2。dp[3]=2+1=3，对应 1+1+1、1+2、2+1。dp[4]=3+2=5。dp[5]=5+3=8。表往下加到第 5 阶时，3 这个格子被读了第二次——第一次是算 dp[4] 的 3+2，第二次是算 dp[5] 的 5+3。递归树里那两次独立的 f(3)，在这里是同一个格子：读两次、算一次。演示场景逐步填的就是这张表。
算 dp[i] 时只用得到前两个值，整张表可以收成两个滚动变量。先握住 a=1（dp[1]）、b=2（dp[2]）。i=3：新值 1+2=3，窗口变成 2 和 3。i=4：2+3=5。i=5：3+5=8。答案还是 8。f(1)、f(2) 已经滑出窗口，但它们的贡献早写进后面的数里了。可滚动不是随便扔历史，是转移窗口永远只有两格。
重叠，不是独立到 n-1、n-2 的方式是历史事实，与之后怎么走无关，所以可以复用。复用的前提是同一问被问第二次：f(5) 和 f(4) 都要 f(3)。独立的子问题走分治；重叠的子问题才把答案存下来。
Go：滚动两个变量
func climbStairs(n int) int {if n <= 2 { return n }a, b := 1, 2 // dp[i-2], dp[i-1]for i := 3; i <= n; i++ {a, b = b, a+b}return b}
1n≤2 直接返回 n：1 级 1 种，2 级 2 种。不要进循环去碰并不存在的第 0 阶。
2a、b 分别是窗口里的 dp[i-2]、dp[i-1]。n=5 时循环走三次，b 依次变成 3、5、8。
3a, b = b, a+b 是「昨天的 b 变成今天的 a」。重叠的那一格没有丢掉：算 8 时用到的正是留下的 3 和 5。
4每个 i 只加一次，时间 O(n)；只留两个整数，空间 O(1)。
总结
f(5)=f(4)+f(3)=5+3=8。f(3) 被问两次，只算一次。
- 最后一步只可能是 1 或 2，两类方案不重叠、不遗漏。主例 5 种加 3 种就是 8 种。
- 重叠子问题：递归树里 f(3) 出现两次，答案都是 3。记住格子，读两次、算一次。
- 转移只用前两格，两个变量滚动即可。不要和「切开就互不来往」的分治混成一件事。