22 lines
422 B
C++
22 lines
422 B
C++
// 斐波那契数列记忆化递归
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
const ll p = 1e9 + 7;
|
|
const int N = 1e5 + 3;
|
|
ll dep[N];
|
|
|
|
ll fib(int a){
|
|
if(a <= 2) return 1;
|
|
if(dep[a] != -1) return dep[a] % p;
|
|
return dep[a] = (fib(a-1) + fib(a-2)) % p;
|
|
}
|
|
int main(){
|
|
fill(dep, dep + N, -1);
|
|
int n; cin >> n;
|
|
cout << fib(n) << endl;
|
|
return 0;
|
|
}
|
|
/*
|
|
1 1 2 3 5 8 13 21 34
|
|
*/ |