Python递归实现爬楼梯问题

爬楼梯问题是经典的动态规划问题，但也可以用递归解决。假设一共有n个台阶，可以一次爬1个或2个，那么到达第n个台阶的方法数就等于到达第n-1个和第n-2个台阶的方法数之和。因此，我们可以写出递归代码：

def climbStairs(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return climbStairs(n-1) + climbStairs(n-2)

这个递归函数接收一个整数n，表示台阶数，返回一个整数，表示到达第n个台阶的方法数。我们首先处理特殊情况：当台阶数为0或1时，只有一种到达方法，直接返回1。否则，返回到达第n-1个和第n-2个台阶的方法数之和。

不过，这个递归函数的时间复杂度为指数级，因为对于某些台阶数，我们会重复计算其子问题。例如，当n=4时，climbStairs(3)和climbStairs(2)会被分别计算两次，因此我们需要想办法优化。

一种优化方法是使用记忆化搜索，即在递归过程中记录已经计算过的子问题的结果，避免重复计算。可以使用一个列表memo来存储，memo[i]表示到达第i个台阶的方法数。如果memo[i]不为None，说明已经计算过，直接返回memo[i]即可；否则，进行递归计算，并将结果存入memo[i]中。

def climbStairs(n: int) -> int:
    memo = [None] * (n+1)
    return helper(n, memo)

def helper(n: int, memo: List[int]) -> int:
    if n == 0 or n == 1:
        return 1
    if memo[n] is not None:
        return memo[n]
    memo[n] = helper(n-1, memo) + helper(n-2, memo)
    return memo[n]

另一种优化方法是使用迭代，即从小到大计算每个子问题，避免重复计算。可以用两个变量a和b来分别记录到达第i和第i+1个台阶的方法数，然后迭代n-2次，每次用a+b更新a和b的值。

def climbStairs(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    a, b = 1, 1
    for i in range(2, n+1):
        c = a + b
        a, b = b, c
    return b

这个迭代函数的时间复杂度为O(n)，空间复杂度为O(1)。用递归实现的话，时间复杂度为O(2^n)，空间复杂度为O(n)（递归栈的深度）。