爬楼梯问题：求解所有上台阶方法的C++代码实现

问题描述: 小明的面前有一个'n'级的台阶，他每次可以上一级或是两级，现在他想知道每一种上台阶的方法，请你告诉他。

具体要求:

请你求出有多少种上台阶的方法；
对于每一种上台阶的方法，请你用数字表示每一步的台阶数，并将不同方法按字典序输出。

例如:

当'n = 3'时，可行方法为 '111', '12', '21'（3种），其中 '111' 表示第一步走1个台阶，第二步走1个台阶，第三步走1个台阶，因此按字典序输出：

111
12
21

输入格式: 输入一个正整数'n'，表示台阶数量。

输出格式: 第一行输出一个数'm'，表示上台阶的方法数。之后'm'行每行输出一个由'1'、'2'组成的字符串，表示一种上台阶的方法。

输入样例:

输出样例:

C++代码实现:

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

// 递归函数，求解上台阶的方法数
int climbStairs(int n, vector<vector<int>>& memo) {
    if (n <= 2) {
        return n;
    }
    if (memo[n][0] != -1) {
        return memo[n][0]; // 如果已经计算过了，直接返回结果
    }
    int ans = climbStairs(n-1, memo) + climbStairs(n-2, memo); // 分别计算上一级和上两级台阶的方法数
    memo[n][0] = ans; // 将结果存入备忘录
    return ans;
}

// 递归函数，求解每一种上台阶的方法
void getStairs(int n, int cur, string& path, vector<string>& res) {
    if (cur == n) {
        res.push_back(path); // 如果已经到达最后一级台阶，将当前路径加入结果集
        return;
    }
    if (cur+1 <= n) {
        path.push_back('1'); // 上一级台阶
        getStairs(n, cur+1, path, res);
        path.pop_back();
    }
    if (cur+2 <= n) {
        path.push_back('2'); // 上两级台阶
        getStairs(n, cur+2, path, res);
        path.pop_back();
    }
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> memo(n+1, vector<int>(1, -1)); // 备忘录，用于存储已经计算过的结果
    int num = climbStairs(n, memo); // 求解上台阶的方法数

    vector<string> res;
    string path;
    getStairs(n, 0, path, res); // 求解每一种上台阶的方法

    cout << num << endl;
    sort(res.begin(), res.end()); // 按字典序排序
    for (string s : res) {
        cout << s << endl;
    }

    return 0;
}

代码解析:

climbStairs(int n, vector<vector<int>>& memo) 函数
- 该函数使用递归方法计算上'n'级台阶的方法数。
- 递归的基准情况是当'n <= 2'时，方法数为'n'。
- 使用备忘录'memo'存储已经计算过的结果，避免重复计算，提高效率。
- 递归公式为: climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)，即到达第'n'级台阶的方法数等于到达第'n-1'级台阶的方法数加上到达第'n-2'级台阶的方法数。
getStairs(int n, int cur, string& path, vector<string>& res) 函数
- 该函数使用递归方法获取所有上台阶的方法，并将结果存储在'res'中。
- 递归的基准情况是当'cur == n'时，表示已经到达最后一级台阶，将当前路径'path'加入结果集'res'中。
- 递归过程中，分别尝试走1级和2级台阶，并递归调用自身继续探索。
main() 函数
- 获取输入的台阶数量'n'。
- 初始化备忘录'memo'。
- 调用climbStairs()函数计算方法数'num'。
- 调用getStairs()函数获取所有上台阶的方法并存储在'res'中。
- 对'res'进行字典序排序。
- 输出方法数'num'和所有方法。

代码特点:

使用递归和备忘录技术，有效地解决了爬楼梯问题。
递归函数climbStairs()用于计算方法数，而getStairs()函数用于获取所有方法。
使用vector<string>存储所有方法，并使用sort()函数对结果进行字典序排序。
使用string存储每种方法，方便输出。

代码优势:

清晰易懂，易于理解代码逻辑。
效率较高，避免了重复计算。
结果按字典序排序，符合题意要求。

总结:

本文展示了使用C++代码解决经典爬楼梯问题的完整解决方案，并详细解析了代码实现和逻辑。代码使用递归和备忘录技术，有效地求解了所有上台阶的方法，并按字典序进行了排序输出。希望本文能够帮助读者理解和解决类似的算法问题。