题解 | #牛牛学数列7#

动态规划解决时间复杂度过高的问题

#include<bits/stdc++.h>
using namespace std;
long long int fib(int k,long long int *fibon){
   
    if(fibon[k]==-1) fibon[k]=(fib(k-1,fibon)+fib(k-2,fibon));
    return fibon[k];
}
int main(){
    int n;
    cin>>n;
    long long int fibs[100];
    fill(fibs,fibs+100,-1);
    fibs[1]=0,fibs[2]=1;
    cout<<fib(n,fibs);
}