Limited access

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];
}

Select an assignment template