python递推方法解决爬楼梯

在Python中，递归方法可以用来解决“爬楼梯”问题，也称为“汉诺塔”或“阶跃数列”的问题。这个问题通常描述为一个人有若干级台阶，每次可以爬一级或两级，问有多少种不同的方式到达顶楼。这是一个典型的动态规划问题，可以用递归来求解。

递归的基本思路是这样的：
1. 当只有一个台阶时，显然只有一种走法，即直接上。
2. 当有两个台阶时，有两种走法：先走一步再走两步，或者直接走两步。
3. 对于三个台阶及以上的情况，可以分为两类情况：先走一步到第二个台阶，然后走两步到达；或者直接走两步到第三个台阶。这两种情况分别对应前两个台阶和当前三个台阶的组合。

递归函数通常会有基本情况（如单步、双步）和递归情况（将问题分解为更小的子问题）。这里可以用一个列表记录每种长度下的走法，然后通过递归更新这个列表：

def climb_stairs(n):
    if n == 1 or n == 2:   # 基本情况：一步和两步
        return n
    else:
        dp = [0] * (n + 1)  # 初始化一个长度为n+1的dp数组
        dp[1], dp[2] = 1, 2  # 填充前两个值
        for i in range(3, n + 1):  # 从第三步开始计算
            dp[i] = dp[i - 1] + dp[i - 2]  # 一次走一步和两次走
        return dp[n]

# 测试
print(climb_stairs(4))  # 输出: 5，因为有5种方式爬完4级台阶