// Program to convert recursive fibonacci into dp

// tc= O(n)

// sc= O(n) + O(n) = stack space + extra array space respectively

import java.util.*;

public class dp {

    public static int func(int n, int[] dp)

    {

         if(n<=1) return n; //base case

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

         return dp[n]= func(n-1,dp) + func(n-2,dp); //compute

    }

    public static void main(String[] args) {

        int n = 5;

        int dp[] = new int[n+1];

        Arrays.fill(dp,-1); // initialise all with -1

        for (int i : dp) {

            System.out.print(i+" "); // output is -1,-1,-1,-1,-1,-1

        }

        System.out.println();

        System.out.println("----");

        System.out.println(func(n,dp)); // output is 5

        System.out.println("----");

         for (int i : dp) {

            System.out.print(i+" "); // output is: -1,-1,1,2,3,5

        }

    }

}