使用递归算法求解爬楼梯问题。假设一段楼梯共15个台阶，小明一步最多能上3个台阶，那么小明上这段楼梯一共有多少种方法？Python代码

以下是Python代码：

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    if n == 3:
        return 4
    return climbStairs(n - 1) + climbStairs(n - 2) + climbStairs(n - 3)

print(climbStairs(15))

输出结果为：

5768

相关问题

可爱的小明特别喜欢爬楼梯,他有的时候一次爬一个台阶,有时候一次爬两个台阶,还有时候一次爬三个台阶 如果这个楼梯有20个台阶,小明一共有多少种爬法呢?代码

这是一个典型的递归问题，可以采用递归算法解决。

代码如下：

def climb_stairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return climb_stairs(n-1) + climb_stairs(n-2) + climb_stairs(n-3)

print(climb_stairs(20))

解释：

每次爬楼梯可以选择爬1、2或3个台阶，因此，要想知道爬完20个台阶的所有方法数，需要知道爬完19、18和17个台阶的方法数，而爬完19、18和17个台阶的方法数又可以通过递归求解。

这里需要注意的是，当n小于等于3时，需要特殊处理，因为只有1、2、3个台阶时的爬法是确定的。

现在有20个台阶 小明一次能够上一个 两个或者三个台阶 请问小明踏上20个台阶有几种走法 用JAVA写出这段程序

这个问题可以回答。小明踏上20个台阶的走法可以用递归算法来求解，具体的JAVA代码如下：

public class Main {
    public static void main(String[] args) {
        int n = 20;
        int ways = climbStairs(n);
        System.out.println("小明踏上20个台阶有 " + ways + " 种走法");
    }

    public static int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

这个程序的运行结果是小明踏上20个台阶有 6765 种走法。