爬楼梯问题解析

在LeetCode中，爬楼梯问题是一个经典的动态规划问题。它主要考察我们对递归和动态规划的理解。

问题描述

假设你正在爬楼梯。每次你可以爬1个或2个台阶。你达到楼顶需要爬的总台阶数是n。请问，有多少种不同的方法可以爬到楼顶？

示例

假设楼梯有5个台阶，那么你可以这样爬：

1, 1, 1, 1, 1
1, 1, 1, 2
1, 2, 1, 1
2, 1, 1, 1
1, 2, 2
2, 1, 2
2, 2, 1
3, 1
1, 3

总共有8种不同的方法可以爬到楼顶。

解题思路

这个问题可以通过递归或动态规划来解决。

递归解法

递归解法比较直观，但是效率较低。其基本思想是：如果楼梯有n个台阶，那么到达第n个台阶的方法数等于到达第n-1个台阶的方法数加上到达第n-2个台阶的方法数。

def climbing_stairs_recursive(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climbing_stairs_recursive(n-1) + climbing_stairs_recursive(n-2)

动态规划解法

动态规划解法效率更高。其基本思想是：将问题分解为子问题，并存储子问题的解，避免重复计算。

def climbing_stairs_dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    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]

扩展阅读

如果你对爬楼梯问题还有更多疑问，可以参考以下链接：