题目

思路

一句话：想走到第 n 级，最后一步要么从 n-1 级跨 1 级，要么从 n-2 级跨 2 级；所以 dp[n] = dp[n-1] + dp[n-2]。

先想最笨的做法：从第 0 级出发，每一步都分「跨 1」「跨 2」两个岔路，一路走到底再计数。写成递归就是 f(n) = f(n-1) + f(n-2)。若不记忆化，同一个 f(n-2) 子树会被反复展开，时间呈指数级；当 n = 45 时根本跑不完。

关键观察：从某一级台阶继续往上爬，后面的走法数只取决于当前站在第几级——你之前是怎么走到这里的，不影响之后还剩多少种走法（这就是无后效性）。因此大问题可以无重叠地切成两个子问题：到达第 n 级的全部路径，按「最后一步是跨 1 还是跨 2」恰好分成两类，两类数量分别是 dp[n-1] 与 dp[n-2]，相加即得 dp[n]。

既然有递推式，就从底向上逐个算，避免重复展开；又因为 dp[i] 只依赖前两项，最后连数组都不用开，用两个滚动变量即可。

解法

先把边界定好：到第 1 级只有 [1] 一种，到第 2 级有 [1,1]、[2] 两种；之后按递推式往后滚。

1. 若 n =
   🔒

   本篇为付费内容

   您已阅读试读部分，购买后即可解锁全文。

   ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。