Skip to content
Advertisement

Fibonacci Memoized/Dynamic Programming in Java

So this is some code to calculate the Fibonacci sequence with memoization. What confuses me is when we check if memo[i]==0. I understand that Java arrays are initialized to zero and thus if memo[i] == 0 this may mean that the computation for memo[i] has not yet occured. However, one of the return values for this fibonacci function is 0. So doesn’t this mean that let’s say if fib(3)=0 (I know it doesn’t but just for the sake of arguement) then everytime we have fib(3) we would wind up recomputing fib(3) because the check is if(memo[i] == 0) right? And if that is the case why can we use if(memo[i] == 0) in this particular code and not wind up recomputing a bunch of values?

int fibonacci(int n){
  return fibonacci(n, new int[n+1]);
}

int fibonacci(int i, int[] memo) {
  if(i == 0 || i == 1) return i;

  if(memo[i] == 0){ //This line does not make sense to me
    memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
  }
  return memo[i];
}

Advertisement

Answer

Since the only case where fib(i) should return 0 is when i = 0, then the test if (memo[i] == 0) is ok—it is never called for a value where 0 is an ambiguous result because of the first line of the function: if (i == 0.

Note what I think is more puzzling is why is the memoization array created in the wrapper call? Yes, the memoization saves computation for a given call, but all that optimization is lost between successive calls to the function.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement