树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。 例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。但是如果第二层楼梯坏了，就只能先走到第一层，再走到第三层；c++代码

你可以使用递归来解决这个问题。下面是一个使用C++编写的示例代码：

#include <iostream>
using namespace std;

int countWays(int n) {
    if (n <= 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return countWays(n - 1) + countWays(n - 2);
}

int main() {
    int n;
    cout << "请输入楼梯的级数：";
    cin >> n;
    int ways = countWays(n);
    cout << "不同的走法数：" << ways << endl;
    return 0;
}

在这个代码中，`countWays`函数使用递归来计算不同的走法数。当楼梯级数为0或1时，只有一种走法；当级数为2时，有两种走法；对于其他级数，可以选择先走一级，然后计算剩余的级数的走法数，或者先走两级，然后计算剩余的级数的走法数。最后将两种情况的走法数相加即可得到总的走法数。

注意，这种解法的时间复杂度是指数级的，因为它会重复计算一些子问题。在实际应用中，可以使用动态规划来优化解法，避免重复计算，从而提高性能。

相关问题

python题目：王老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。

这是一个经典的动态规划问题，通常被称为“爬楼梯”或“阶跃数”。在Python中，你可以通过递推的方式解决这个问题。首先，我们需要初始化两个变量，分别表示走1级和2级到达第n级的情况。然后，对于每一级，我们可以从上一级加一或者从上两级加二来计算当前级别的走法。

以下是Python代码示例：

def climbStairs(n):
    if n == 1 or n == 2:  # 基本情况，如果只有1级或2级，只有一种走法
        return n
    else:
        dp = [0] * (n + 1)  # 创建一个数组dp，用于存储每个台阶的走法数
        dp[1] = 1  # 第1级有1种走法
        dp[2] = 2  # 第2级有2种走法

        for i in range(3, n+1):  # 从第三级开始，每一步都有两种选择（上1级或2级）
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]  # 返回最后一级的走法数

# 测试函数
stair_count = int(input("请输入楼梯的级数: "))
print(f"不同的走法共有 {climbStairs(stair_count)} 种。")

python王老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。 例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。

这个问题可以通过动态规划解决。我们可以定义一个数组`dp`，其中`dp[i]`表示到达第`i`级台阶的不同走法数。对于每一步，可以从上一层（即`dp[i-1]`）或上两层（即`dp[i-2]`）走上来，所以有`dp[i] = dp[i-1] + dp[i-2]`。初始状态为`dp[0] = 1`（因为走到第一级只有一种方式，就是不走），`dp[1] = 1`（也只有一种方式，就是走一次）。以下是Python代码实现：

def climb_stairs(n):
    dp = [0] * (n+1)
    dp[0], dp[1] = 1, 1  # 初始化前两个值
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]  # 动态规划计算走法
    return dp[n]

stair_count = climb_stairs(int(input("请输入楼梯的级数：")))
print(f"不同的走法数为：{stair_count}")

当你运行这个程序，它将根据输入的楼梯级数返回不同的走法数。