假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法?Python 递推法和递归法两种结果

对于这个问题，小明一步最多能上3个台阶，这意味着他可以用单步、两步或三步的方式到达第n个台阶。这其实是一个经典的动态规划问题，适合使用递推法求解，因为它有一个明确的“状态转移”规则。

**递推法（Python）**：

def climb_stairs(n):
    # 初始化基础情况
    if n == 1 or n == 2:
        return n
    
    # 使用递推公式 F(n) = F(n-1) + F(n-2) + F(n-3)
    # 当n >= 3时，F(n)包括了前三个台阶的所有组合
    dp = [0] * (n+1)
    dp[1], dp[2], dp[3] = 1, 2, 3
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        
    return dp[n]

# 求15个台阶的方案数
staircases = climb_stairs(15)

**递归法（Python）**虽然也能解决问题，但由于会存在大量的重复计算，效率较低，不建议用于大规模数据：

def recursive_climb_stairs(n):
    if n <= 3:
        return n
    else:
        return recursive_climb_stairs(n-1) + recursive_climb_stairs(n-2) + recursive_climb_stairs(n-3)

# 注意递归法需要避免无限递归，并且不适合大规模数据，因为会浪费大量时间在重复计算上。
# staircases = recursive_climb_stairs(15); 不推荐使用