斐波那契 Memoized/Dynamic 编程 Java

Question

所以这是一些用记忆计算斐波那契数列的代码。令我困惑的是当我们检查 memo[i]==0 时。我知道 Java 数组被初始化为零，因此如果 memo[i] == 0 这可能意味着 memo[i] 的计算尚未发生。然而，这个斐波那契函数的 return 值之一是 0。所以这是否意味着如果 fib(3)=0 （我知道它不是，但只是为了争论）然后每次我们有 fib(3) 我们都会重新计算 fib(3) 因为检查是 if(memo[i] == 0) 对吗？如果是这种情况，为什么我们可以在此特定代码中使用 if(memo[i] == 0) 而不是重新计算一堆值？

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

Answer 1

因为 fib(i) 应该 return 0 的唯一情况是当 i = 0 时，那么测试 if (memo[i] == 0) 是可以的——它永远不会被调用为 0 的值由于函数第一行的结果不明确：if (i == 0.

请注意，我认为更令人费解的是为什么在包装器调用中创建了记忆数组？是的，记忆化为 given 调用节省了计算量，但所有优化都在函数的连续调用之间丢失了。

Answer 2

if(memo[i]==0)

如果块意味着如果 fibonacci(n) 尚未计算（在这种情况下，第 i 个索引中的值将为 0），则计算 fibonacci(n) 和缓存的值，但如果它已经已经计算过并且stored/cached（在这种情况下第 i 个索引中的值不会为 0），不要再次计算。

这是因为，int 数组值默认初始化为 0。您可以在这里查看：Any shortcut to initialize all array elements to zero?

斐波那契 Memoized/Dynamic 编程 Java

Fibonacci Memoized/Dynamic Programming in Java

java

recursion

dynamic-programming

fibonacci

memoization