Python爬楼梯算法:递归与动态规划代码实现

七月
七月
发布时间:2026-11-20 | 9人浏览过
原创

深入解析Python爬楼梯算法的核心原理与代码实现。从朴素递归的重叠子问题分析,到自顶向下的记忆化搜索,再到自底向上的动态规划及其O(1)空间复杂度压缩优化。

假设你正在爬一段共有 n 阶的楼梯,每次只能迈上 1 个台阶或者 2 个台阶。请问爬到楼顶共有多少种不同的走法?这就是经典的“爬楼梯”问题(Climbing Stairs)。虽然题目描述非常生活化,但它不仅是各大编程面试的高频常客,更是透彻理解递归思想、重叠子问题以及动态规划(Dynamic Programming)状态转移模型最理想的切入点。

本文将使用 Python 语言,带领读者从最自然的数学归纳出发,先构建朴素递归模型,观察调用栈中的重复计算;接着引入记忆化搜索消除冗余;最后演进到自底向上的动态规划解法,并完成空间复杂度仅为 O(1) 的滚动变量优化。

一、问题模型推导与状态转移原理

很多初学者在遇到这道题目时,容易陷入枚举具体每一步走向的误区,导致列举过程非常繁琐。实际上,解决这个问题的核心在于倒推最后一步的选择。

假设我们已经到达了第 n 阶台阶,由于规则限定每次只能迈 1 步或 2 步,那么到达第 n 阶的最后一次动作只可能存在两种情况:

  • 从第 n - 1 阶迈上 1 步到达第 n 阶;
  • 从第 n - 2 阶迈上 2 步到达第 n 阶。

显然,到达第 n - 1 阶的所有可能走法,和到达第 n - 2 阶的所有可能走法之间是互斥且完备的。因此,到达第 n 阶的方法总数 f(n),恰好等于到达第 n - 1 阶的方法数与到达第 n - 2 阶的方法数之和:

f(n) = f(n - 1) + f(n - 2)

再考虑基准条件(Base Cases):当台阶数 n = 1 时,只有 1 种走法(迈 1 步);当台阶数 n = 2 时,有两种走法(走两次 1 步,或直接走一次 2 步)。这就是数学上著名的斐波那契数列模型。

Python爬楼梯算法:递归与动态规划代码实现
图 1:爬楼梯算法的状态转移与数学推导逻辑

二、解法一:朴素递归(自顶向下)

既然得到了递推关系 f(n) = f(n - 1) + f(n - 2),最直接的编程方式就是利用函数自调用,写出自顶向下的纯递归代码:

def climb_stairs_recursive(n: int) -> int:
    """
    朴素递归实现(存在大量重复计算,仅用于演示原理)
    时间复杂度: O(2^n)
    空间复杂度: O(n) (系统调用栈开销)
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# 测试运行
if __name__ == "__main__":
    n = 5
    print(f"爬 {n} 阶台阶的方法数: {climb_stairs_recursive(n)}")
    # 示例输出: 爬 5 阶台阶的方法数: 8

为什么朴素递归会严重超时?

上述代码逻辑完全符合数学公式,但是当输入规模 n > 35 时,程序运行时间将以指数级暴增,甚至直接卡死。原因就在于重叠子问题(Overlapping Subproblems)。

在以 f(5) 为例的递归树中,为了计算 f(5),需要分别计算 f(4) 和 f(3);而在展开 f(4) 时,又会再次调用 f(3)。随着树形深度的增加,相同的子函数被无休止地重复执行。整棵递归树的高度为 n,节点总数达到 2n 级别,其时间复杂度为极为恐怖的 O(2n)。

Python爬楼梯算法:递归与动态规划代码实现
图 2:纯递归产生的重叠子问题分析与调用爆炸演示

三、解法二:记忆化搜索(自顶向下 + 备忘录)

既然重复计算是导致性能低下的罪魁祸首,一个显而易见的改进策略就是:每次计算出某个台阶的答案后,把它保存在哈希表或列表中;下次再需要时直接读取,不再重新递归。

这种方法称为“记忆化搜索”(Memoization),它保留了自顶向下的清晰逻辑,同时将每个状态的求解次数严格降为 1 次。

from typing import Dict

def climb_stairs_memo(n: int, memo: Dict[int, int] = None) -> int:
    """
    记忆化搜索(自顶向下递归 + 备忘录缓存)
    时间复杂度: O(n)
    空间复杂度: O(n) (备忘录字典与系统调用栈)
    """
    if memo is None:
        memo = {}
    
    # 边界条件
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
        
    # 查询备忘录
    if n in memo:
        return memo[n]
        
    # 计算并缓存
    memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
    return memo[n]

# 或者使用 Python 内置的高性能装饰器:
from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs_lru(n: int) -> int:
    if n <= 2:
        return max(0, n)
    return climb_stairs_lru(n - 1) + climb_stairs_lru(n - 2)

# 测试执行
if __name__ == "__main__":
    print("记忆化搜索求解 n=40:", climb_stairs_memo(40))
    # 示例输出: 记忆化搜索求解 n=40: 165580141
核心提醒

在 Python 中,通过 @functools.lru_cache 可以在不侵入原有递归结构的情况下自动实现状态缓存。但请注意,递归解法始终受制于 Python 的默认最大递归深度(通常为 1000)。当 n 达到数千时,会触发 RecursionError: maximum recursion depth exceeded。若要彻底摆脱栈溢出风险,必须转向自底向上的迭代方式。

四、解法三:经典动态规划(自底向上数组法)

动态规划的核心思想是不再自顶向下发散,而是自底向上(Bottom-Up)逐步推导。我们从已知最小的问题出发:先确定 1 阶和 2 阶的解,再像搭积木一样依次计算 3 阶、4 阶……直到填满至第 n 阶。

算法步骤

  1. 分配状态数组:创建长度为 n + 1 的列表 dp,其中 dp[i] 存放爬到第 i 阶的方法数。
  2. 设定基准值:dp[1] = 1,dp[2] = 2。
  3. 状态转移迭代:从 i = 3 循环遍历到 n,每一次执行 dp[i] = dp[i - 1] + dp[i - 2]。
  4. 返回最终结果:返回 dp[n]。
def climb_stairs_dp(n: int) -> int:
    """
    经典动态规划数组法
    时间复杂度: O(n)
    空间复杂度: O(n)
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    # 初始化 dp 数组,长度为 n + 1 以方便按台阶序号直接索引
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# 示例验证
if __name__ == "__main__":
    for i in range(1, 6):
        print(f"台阶数: {i}, 走法数: {climb_stairs_dp(i)}")
    # 示例输出:
    # 台阶数: 1, 走法数: 1
    # 台阶数: 2, 走法数: 2
    # 台阶数: 3, 走法数: 3
    # 台阶数: 4, 走法数: 5
    # 台阶数: 5, 走法数: 8

五、解法四:状态压缩优化(空间复杂度降至 O(1))

细心观察动态规划的更新过程,我们会发现一个非常关键的细节:计算当前的 dp[i] 时,仅仅需要紧挨着它的前两个状态 dp[i - 1] 和 dp[i - 2]。更早之前的状态(例如 dp[1]、dp[2])在后续计算中根本不再参与。

这意味着我们完全没有必要维护一个长度为 n + 1 的大数组!只需要声明两个变量来记录“前一步”和“前两步”的值,并在每一步计算后向前“滚动滑动”即可。这就是算法设计中非常著名的状态压缩(State Compression)技巧。

Python爬楼梯算法:递归与动态规划代码实现
图 3:自底向上状态转移与空间复杂度降至 O(1) 的滚动变量滑动图解
def climb_stairs_optimized(n: int) -> int:
    """
    空间最优的滚动变量解法
    时间复杂度: O(n)
    空间复杂度: O(1) (常数级额外内存空间)
    """
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2

    # 分别对应到达前前项 (i-2) 与前一项 (i-1) 的走法总数
    prev2 = 1  # 对应 n=1
    prev1 = 2  # 对应 n=2

    for _ in range(3, n + 1):
        current = prev1 + prev2
        # 向前滚动更新状态
        prev2 = prev1
        prev1 = current

    return prev1

# 边界测试与大数值测试
if __name__ == "__main__":
    test_cases = [1, 2, 3, 5, 10, 50]
    for case in test_cases:
        print(f"台阶数 n = {case:2d} -> 走法方案数 = {climb_stairs_optimized(case)}")
    # 示例输出:
    # 台阶数 n =  1 -> 走法方案数 = 1
    # 台阶数 n =  2 -> 走法方案数 = 2
    # 台阶数 n =  3 -> 走法方案数 = 3
    # 台阶数 n =  5 -> 走法方案数 = 8
    # 台阶数 n = 10 -> 走法方案数 = 89
    # 台阶数 n = 50 -> 走法方案数 = 20365011074

六、算法全维度对比与总结

为了让读者更清晰地掌握这四种算法形态的演进脉络,我们将它们的时空开销、核心思想及优缺点汇总如下:

Python爬楼梯算法:递归与动态规划代码实现
图 4:爬楼梯算法各解法复杂度及方案横向对比总结
解法方案 核心思路 时间复杂度 空间复杂度 适用场景及局限
朴素递归 直接自顶向下展开公式 O(2n) O(n) 仅适合教学理解基本原理,n>35 时完全不可用。
记忆化搜索 自顶向下 + 哈希表或数组缓存 O(n) O(n) 适合思维偏向递归推导的场景;受限于语言的最大递归深度。
动态规划数组 自底向上迭代填表 O(n) O(n) 标准解法,容易扩展到更复杂的约束条件或需要还原路径的场景。
滚动变量优化 自底向上 + 仅保留前两个状态 O(n) O(1) 最优解,时空效率极致,是工业界实现与算法面试的标杆答卷。

从纯递归到动态规划,再到滚动变量状态压缩,解决爬楼梯算法的这一演进路径,生动地展示了算法优化的经典方法论:识别重复工作、建立状态缓存、转化计算方向、压缩冗余存储。掌握这套思路,未来在遇到“打家劫舍”、“斐波那契数列”、“不同路径”等一系列动态规划问题时,便能游刃有余、融会贯通。

相关专题:

本站声明

本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。

Python 相关产品和应用

全部下载

专题列表