1. Introduction

The two common dynamic programming approaches are:
- Memoization: Known as the “top-down” dynamic programming, usually the problem is solved in the direction of the main problem to the base cases.
- Tabulation: Known as the “bottom-up ” dynamic programming, usually the problem is solved in the direction of solving the base cases to the main problem

• Bottom is 0 and top is n

//Top to bottom O(n) for both
import java.util.*;
class TUF{
	static int f(int n, int[] dp){
	    if(n<=1) return n;
	    
	    if(dp[n]!= -1) return dp[n];
	    return dp[n]= f(n-1,dp) + f(n-2,dp);
	}
	
	public static void main(String args[]) {
	
	  int n=5;
	  int dp[]=new int[n+1];
	  Arrays.fill(dp,-1);
	  System.out.println(f(n,dp));
	  
	}
}
 
// Bottom Up O(n) for both
import java.util.*;
class TUF{
	public static void main(String args[]) {
	
	  int n=5;
	  int dp[]=new int[n+1];
	  Arrays.fill(dp,-1);
	  dp[0]= 0;
	  dp[1]= 1;
	  
	  for(int i=2; i<=n; i++){
	      dp[i] = dp[i-1]+ dp[i-2];
	  }
	  System.out.println(dp[n]);
	  
	  
	}
}
 
//Space can further be optimized O(n)
 
import java.util.*;
class TUF{
	public static void main(String args[]) {
	  int n=5;
	  int prev2 = 0;
	  int prev = 1;
	  
	  for(int i=2; i<=n; i++){
	      int cur_i = prev2+ prev;
	      prev2 = prev;
	      prev= cur_i;
	  }
	  System.out.println(prev);
	  
	}
}