题目描述

小明爬楼梯回家，一共有 n 级台阶，他每次只能跨 1 级或者跨 2 级台阶。请你编程计算：小明一共有多少种不同的方式可以爬到楼顶？

输入格式

输入一个正整数 n（1≤n≤30），代表台阶总数。

输出格式

输出一个整数，表示爬到楼顶的总方法数。

3

3

解释：1+1+1、1+2、2+1 共 3 种

5

8

数据范围

$1 \leq n \leq 30$

视频解析

主讲人

时间：2025年 11 月 8 日（周六） 20 时。 T1 爬楼梯

递推解法分析

我们先思考：爬到第 n 阶的最后一步，只有两种可能：

最后一步爬了 1 阶 → 说明之前已经爬到了第 n-1 阶，再爬1阶到楼顶；

最后一步爬了 2 阶 → 说明之前已经爬到了第 n-2 阶，再爬2阶到楼顶。

由此可推出核心递推公式：

dp[n] = dp[n-1] + dp[n-2]

其中 dp[n] 表示“爬到第 n 阶的方法数”。

补充边界条件（base case）：

当 n = 1 时，只有1种方法（直接爬1阶），所以 dp[1] = 1；

当 n = 2 时，有2种方法，所以 dp[2] = 2。

举个例子（n=5）：

dp[3] = dp[2] + dp[1] = 2 + 1 = 3

dp[4] = dp[3] + dp[2] = 3 + 2 = 5

dp[5] = dp[4] + dp[3] = 5 + 3 = 8

和示例结果一致，验证思路正确。

递归解法分析

爬楼梯—递归分析 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。

示例 1：

输入： 1
输出： 1
解释： 有一种方法可以爬到楼顶。
方法1：1 阶

示例 2：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
方法1：1 阶 + 1 阶
方法2：2 阶

继续向后分析，我们会得到：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
方法1：1 阶 + 1 阶 + 1 阶
方法2：1 阶 + 2 阶
方法3：2 阶 + 1 阶

输入： 4
输出： 5
解释： 有5种方法可以爬到楼顶。
方法1：1 阶 + 1 阶 + 1 阶 + 1 阶
方法2：1 阶 + 1 阶 + 2 阶
方法3：1 阶 + 2 阶 + 1 阶
方法4：2 阶 + 1 阶 + 1 阶
方法5：2 阶 + 2 阶

输入： 5
输出： 8
解释： 有5种方法可以爬到楼顶。
方法1：1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
方法2：1 阶 + 1 阶 + 1 阶 + 2 阶
方法3：1 阶 + 1 阶 + 2 阶 + 1 阶
方法4：1 阶 + 2 阶 + 1 阶 + 1 阶
方法5：1 阶 + 2 阶 + 2 阶
方法6：2 阶 + 1 阶 + 1 阶 + 1 阶
方法7：2 阶 + 1 阶 + 2 阶
方法8：2 阶 + 2阶 + 1 阶

总结一下上述的内容：

当1层楼梯时，有1种方法，表示为：f(1) = 1
当2层楼梯时，有2种方法，表示为：f(2) = 2
当3层楼梯时，有3种方法，表示为：f(3) = f(2) + f(1) = 3
当4层楼梯时，有5种方法，表示为：f(4) = f(3) + f(2) = 5
当5层楼梯时，有8种方法，表示为：f(5) = f(4) + f(3) = 8
…（以此类推）

当n层楼梯时，有f(n)种方法，表示为：f(n) = f(n-1) + f(n-2) = ?