Ques :-  Find the nth Fibonacci number

 

Top Down Approach

 

#include<bits/stdc++.h>

 

using namespace std;

#define MAX 30

int dp[MAX];

int calculate_fib(int n){

   if(n<2)

         return n;

   if(dp[n] != -1){

   return dp[n];

   }

   int ans = calculate_fib(n-1) + calculate_fib(n-2);

   return dp[n] = ans;

}

 

int main(){

   int n;

   cin>>n;

   for(int i = 0; i<= n; i++)

   dp[i] = -1;

   int ans = calculate_fib(n);

   cout<<ans<<endl;

}

Bottom up Approach

 

dp[0] = 0;

dp[1] = 1;

for(int i = 2; i<=N; i++)

   dp[i] = dp[i-1] + dp[i-2];

cout<<dp[N]<<endl;