?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Moderate

Dynamic Programming: Memoizing Fibonacci

ALGOR-BDEE6I

Which of the below choices demonstrates correct code which memoizes the following recursive algorithm to compute Fibonacci numbers?

public static int fib(int n) {
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) // recursive case
      return fib(n - 1) + fib(n - 2);
}
A
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1)
      f = new int[n + 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      if(f[n] != null)
         return f[n];
      return fib(n - 1) + fib(n - 2);
   }
}
B
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1)
      f = new int[n + 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      f[n] = fib(n - 2) + fib(n - 1);
      return f[n];
   }
}
C
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n - 2)
      f = new int[n - 1];
   if(n == 0) // base cases
      return 0;
   if(n == 1)
      return 1;
   if(n > 1) {  // recursive case
      if(f[n] != null)
         return f[n];
      f[n] = f[n - 1] + f[n - 2]
      return f[n];
   }
}
D
int[] f; // memoization table

public static int fib(int n) {
   if(f == null || f.length < n + 1) {
      f = new int[n + 1];
      f[0] = 0; // base cases
      f[1] = 1;
   }
   if(f[n] != null || n < 2) // recursive case
      return f[n];
   f[n] = fib(n - 2) + fib(n - 1);
   return f[n];
}