70. 爬楼梯

题目链接：70. 爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

核心思考：自顶向下的记忆化搜索

爬楼梯是一个典型的一维动态规划问题。
如果我们要爬到第 n 阶跳板，那么到达它的最后一步路径只能分为两种情况：

1. 从第 n - 1 阶跨一级台阶上来。
2. 从第 n - 2 阶跨两级台阶直接上来。

这代表着到达总阶数的方法种数，就等于两者的求和。这可以表示为状态转移递推公式：f(n) = f(n-1) + f(n-2)。

在 Python 中，我们可以采用非常简洁的自顶向下的递归来实现这一逻辑。为避免传统递归在计算 f(n-1) 和 f(n-2) 时引发重复的重叠子问题计算，我们可以依赖 Python 内置的 @cache 装饰器，直接将以往运算过的返回值进行全局哈希缓存加速机制（即记忆化递归）。

解题思路 (Python)

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dfs(i):
            if i <= 1:
                return 1
            return dfs(i-1) + dfs(i-2)
        
        return dfs(n)

复杂度分析

• 时间复杂度：$O(N)$。得益于 @cache 提供的记忆化，从 $1$ 到 $n$ 的每个层级状态都只进行一次核心计算。
• 空间复杂度：$O(N)$。递归操作具有栈深的消耗，同时内置字典将需要 O(N) 规模的额外容量来缓存各状态反馈。