题解 | N阶楼梯上楼问题

#include<iostream>
using namespace std;

const int MAX = 100;


int f[MAX];
bool visit[MAX];

int Fib(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else if (visit[n]) { // 如果已经访问过
        return f[n];
    } else {
        f[n] = Fib(n - 1) + Fib(n - 2);
        visit[n] = true;
        return f[n];
    }
}

int main() {
    int N;
    while (cin >> N) {
        for (int i = 0; i < MAX; i++) { // 初始化visit数组
            visit[i] = false;
        }

        // 获取结果
        int answer = Fib(N);
        cout << answer << endl;
    }
}

递归+记忆化搜索也可以解决问题