题解 | 牛牛学数列5

#include <bits/stdc++.h>
using namespace std;

int f(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return f(n-1) + f(n-2);
}

int main() {
    int a;
    cin >> a;
    cout << f(a) << endl;
    return 0;
}
下面的更好，时间复杂度o（n）
#include <bits/stdc++.h>
using namespace std;

int f(int n) {
    if (n == 1 || n == 2) return 1;
    int a = 1, b = 1; 
    int res;
    for (int i = 3; i <= n; ++i) {
        res = a + b;
        a = b;        
        b = res;      
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}