class Solution {
public:
    int climbStairs(int n) {
        int a = 0, b = 1;
        for (int i = 1; i <= n; i ++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
};

另外如果不需要写的这么统一，可以这样。 a b 的初值分别就是 第 1 2 楼梯的不同爬法数

class Solution {
public:
    int climbStairs(int n) {
        if (n < 3) return n;
        int a = 1; // 第一阶楼梯
        int b = 2; // 第二阶楼梯
        for (int i = 3; i <= n; i ++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
};

默认做法

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i ++) {
            dp[i] = dp[i - 1]  + dp[i - 2];
        }
        return dp[n];
    }
};

完全背包解法

class Solution {
public:
    // 完全背包解法 排列版
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int j = 0; j <= n; j ++) { // 遍历容量
            for (int i = 1; i <= 2; i ++) { // 遍历物品
                if (j >= i) dp[j] += dp[j - i];
            }
        }
        return dp[n];
    }
};

打印所有解法 DFS

main

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> res;
vector<int> path;

const int n = 10;

void dfs(int i) {
    if (i >= n) return;
    if (i == n - 1) {
        res.push_back(path);
        return;
    }

    // 1
    path.push_back(1);
    dfs(i + 1);
    path.pop_back();

    // 2
    path.push_back(2);
    dfs(i + 2);
    path.pop_back();
}

int main() {
    dfs(0);
    for (const auto& way : res) {
        for (auto step : way) {
            cout << step << " ";
        }
        cout << endl;
    }

    return 0;
}

test

#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

int main() {
    vector<vector<int>> nums;
    // get 1 line
    int x;
    vector<int> line;
    while (cin >> x) {
        line.push_back(x);
        if (cin.get() == '\\n') {
            nums.push_back(line);
            line.clear();
        }
    }

    for (const auto& rows : nums) {
        int sum = 0;
        for (auto x : rows) {
            sum += x;
        }
        if (sum != 10) {
            cout << "false" << endl;
        }
    }
    cout << "true" << endl;

    return 0;
}

g++ main.cpp -o main && ./main > result.txt
g++ test.cpp -o test && ./test < result.txt