台阶爬行问题：C++代码实现

台阶爬行问题：C++ 代码实现

假设你面前有一座 n 级台阶，你每次可以上一级或两级台阶。现在你想要知道所有上台阶的方法，并按照字典序输出。

问题分析：

这道题可以用动态规划的思想解决。我们可以用递归来求解，但递归会重复计算很多子问题，导致效率低下。动态规划则可以通过保存已经计算过的子问题结果来提高效率。

代码实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> climbStairs(int n) {
    vector<string> res;
    if (n <= 0) {
        return res;
    }

    if (n == 1) {
        res.push_back('1');
        return res;
    }

    if (n == 2) {
        res.push_back('11');
        res.push_back('2');
        return res;
    }

    vector<string> prev = climbStairs(n-1);
    for (string s : prev) {
        res.push_back(s + '1');
    }

    vector<string> prevPrev = climbStairs(n-2);
    for (string s : prevPrev) {
        res.push_back(s + '2');
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    vector<string> res = climbStairs(n);
    cout << res.size() << endl;
    for (string s : res) {
        cout << s << endl;
    }
    return 0;
}

代码说明：

1. 函数 climbStairs(int n) 用于计算所有上 n 级台阶的方法。
2. 当 n 为 0 或 1 时，只有一种方法，分别为空字符串和 '1'。
3. 当 n 为 2 时，有两种方法，分别为 '11' 和 '2'。
4. 当 n 大于 2 时，我们利用递归来求解。首先，我们调用 climbStairs(n-1) 来获取所有上 n-1 级台阶的方法，并将每个方法末尾添加 '1'，得到所有上 n 级台阶的第一种方法。
5. 接着，我们调用 climbStairs(n-2) 来获取所有上 n-2 级台阶的方法，并将每个方法末尾添加 '2'，得到所有上 n 级台阶的第二种方法。
6. 最后，我们将两种方法合并，并按照字典序输出。

运行结果：

3
111
12
21

总结：

本文介绍了如何使用 C++ 代码来解决台阶爬行问题，并解释了代码的实现过程。通过学习此代码，你可以了解动态规划的基本思想以及递归的使用方法。希望这篇文章能对你有所帮助！