爬楼梯c++c++c+

Question

描述

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

输入描述

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1≤N≤30。

输出描述

不同的走法数，每一行输入对应一行输出。

用例输入 1

5
8
10
用例输出 1

8
34
89

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以使用动态规划的方法。定义一个数组dp，其中dp[i]表示到达第i级楼梯的不同走法数。根据题目描述，到达第i级楼梯有以下两种情况：

1. 从第(i-1)级楼梯走一步到达，此时的方法数是dp[i-1]。
2. 从第(i-2)级楼梯走两步到达，此时的方法数是dp[i-2]。

因此，我们可以得到递推关系式：

dp[i] = dp[i-1] + dp[i-2];

初始条件是：

dp[0] = 1; // 到达第0级楼梯有一种方式（不动）
dp[1] = 1; // 到达第1级楼梯有一种方式（走一步）

接下来是一个C++程序实现这个算法：

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break; // 输入结束标志，这里假设0表示结束输入

        vector<int> dp(n + 1, 0); // 初始化dp数组
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) { // 从第2级开始计算
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        cout << dp[n] << endl;
    }
    
    return 0;
}

这段代码首先读取输入的楼梯级数n，然后使用动态规划计算到达第n级楼梯的不同走法数，并将结果输出到新的一行。当输入值为0时，程序会停止读取并退出循环。

运行这段代码，将会得到与给定样例相同的输出：

8
34
89