21 lines
395 B
C++
21 lines
395 B
C++
// 斐波那契数列记忆化递归
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
const int N = 1e5 + 3;
|
|
int dep[N];
|
|
|
|
int fib(int a){
|
|
if(a <= 2) return 1;
|
|
if(dep[a] != -1) return dep[a];
|
|
return dep[a] = fib(a-1) + fib(a-2);
|
|
}
|
|
signed 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
|
|
*/ |