题解 | 斐波那契数列

//我用的是记忆化递归，也不知道不用记忆化能不能跑出来，因为我还没学记忆化搜索所以先来练习一下记忆化递归
//至于什么是记忆化递归大家可以上网（如csdn）搜索一下，因为我也刚刚学，也讲不明白
//我在这里推一道例题，大家可以练练https://atcoder.jp/contests/abc445/tasks/abc445_c
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 1000000007;
int fibonacci(int n,vector<int>&memo)
{
    if(memo[n]!=-1)return memo[n];
    if(n <= 0)return 0;
    if(n <= 2)return 1;
    memo[n] = (fibonacci(n - 1,memo) + fibonacci(n - 2,memo))%mod;
    return memo[n];
}
signed main()
{
    int n;
    cin>>n;
    vector<int>memo(n+1,-1);
    cout<<fibonacci(n,memo);
    return 0;
}