给定 n 级台阶，一个人站在地面想要爬楼梯到达顶端。这个人每次可以爬 1 级 或者 2 级 台阶，请计算这个人有多少种方式可以到达顶端。
示例：
> 输入： n = 1
> 输出： 1
> 解释： 只有一种方式可以爬上 1 级台阶。
>
> 输入： n = 2
> 输出： 2
> 解释： 有两种方式可以到达第 2 级台阶：{1, 1} 和 {2}。
>
> 输入： n = 4
> 输出： 5
> 解释： 有五种方式可以到达第 4 级台阶：{1, 1, 1, 1}, {1, 1, 2}, {2, 1, 1}, {1, 2, 1} 和 {2, 2}。
目录
- [朴素方法] 使用 递归 – O(2^n) 时间和 O(n) 空间
- [进阶方法 – 1] 使用 自顶向下 DP (记忆化) – O(n) 时间和 O(n) 空间
- [进阶方法 – 2] 使用 自底向上 DP (制表) – O(n) 时间和 O(n) 空间
- [空间优化] 使用 空间优化 DP – O(n) 时间和 O(1) 空间
- [期望方法] 使用 矩阵快速幂 – O(logn) 时间和 O(1) 空间
[朴素方法] 使用 递归 – O(2^n) 时间和 O(n) 空间
> 在这种方法中，我们观察到要到达第 n 级台阶，可以从第 (n-1) 级或第 (n-2) 级台阶上来。同理，要到达第 (n-1) 级台阶，我们必须知道到达第 (n-2) 级和第 (n-3) 级台阶的方法数，依此类推。通过这种方式，我们可以发现这可以通过递归来完成。
注意： 上述递推关系与斐波那契数列相同。
C++
CODEBLOCK_5135c3fc
C
CODEBLOCK_76f6c13a
Java
CODEBLOCK_4a5adfde
Python
CODEBLOCK_f0c80f22
C#
CODEBLOCK_1e76a99b
JavaScript
CODEBLOCK_05b38859
输出
5
时间复杂度： O(2^n)，因为我们对每一级台阶都进行两次递归调用。
辅助空间： O(n)，因为我们要使用递归栈空间。
[进阶方法 – 1] 使用 自顶向下 DP (记忆化) – O(n) 时间和 O(n) 空间
> 在这种方法中，我们注意到同一个子问题被多次求解。
> 例如，countWays(n) 调用 countWays(n-1) 和 countWays(n-2)，而 countWays(n-1) 又会再次调用 countWays(n-2) 和 countWays(n-3)。
> 在这里，countWays(n-2) 被计算了不止一次。为了避免这种冗余工作，我们可以将子问题的结果存储在 dp 数组中，并在需要时重用它们。
这是 n=4 时重叠子问题的可视化图示。
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/20251030123247865431/frame3291.webp">frame3291
C++
CODEBLOCK_30cc5cef