c++版本

纯递归版本

#include<iostream>
using namespace std;

int fib(int i){
    if(i == 1 || i == 2)
        return 1;
    else{
        return fib(i-1) + fib(i-2);
    }
}
int main(){
    int num;
    cin >> num;
    cout << fib(num)<<endl;
    
    return 0;    
}

动态规划版本

#include<iostream>
using namespace std;

int fib(int n) {
     if (n <2) return n;
     int i = 0;
     int j = 1;
     int m = 0;
     for(int k=2; k<=n; k++) {
         m = (i+j) % 1000000007;
         i = j;
         j = m;
     }
     return m;
    }

int main(){
    int num;
    cin >> num;
    cout << fib(num) << endl;
    
    return 0;    
}