java - Java 中的斐波那契内存/动态编程

Question

这是一些通过内存来计算斐波那契数列的代码。让我困惑的是当我们检查 memo[i]==0 时。我知道 Java 数组被初始化为零，因此如果 memo[i] == 0 这可能意味着 memo[i] 的计算尚未发生。然而，这个斐波那契函数的返回值之一是 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) 应该返回 0 的唯一情况是当 i = 0 时，因此测试 if (memo[i] == 0) 是可以的——它永远不会被调用对于一个值，其中 0 是一个不明确的结果，因为函数的第一行是:if (i == 0.

请注意，我认为更令人困惑的是为什么在包装器调用中创建内存数组？是的，内存可以节省给定调用的计算量，但在连续调用函数之间所有优化都会丢失。