fibonacci number using requirsion/DP

 

//fibonacci number using requirsion

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll fib(ll n)

{

    if(n<=1)return n;

    return (fib(n-1)+fib(n-2));

}

int main()

{

   ll n;

   cin>>n;

   cout<<fib(n)<<endl;

   return 0;

}

//fibonacci number using requirsion/DP

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define N 100005

ll dp[N];

ll fib(ll n)

{

    if(n<=1)return n;

    if(dp[n]!=-1)return dp[n];

    return dp[n]=(fib(n-1)+fib(n-2));

}

int main()

{

    memset(dp,-1,sizeof(dp));

   ll n;

   cin>>n;

   cout<<fib(n)<<endl;

   return 0;

}