题解 | 斐波那契数列

/*递归会出现重复遍历的概况，比如，f(1)可能就会遍历x次
而用动态规划，就会好很多，因为计算过的数据存在数组里面，只需要取就好
极大节约了时间*/


#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll f(ll x)
{
    if(x==0) return 0;
    vector<long long> dp(x+1,0);
    dp[1]=1;
    dp[2]=1;
    for(int i=3;i<=x;i++)
    {
        dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    return dp[x];
}
int main() {
    ll k;
    cin>>k;
    cout<<f(k)<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")