这是一些通过内存来计算斐波那契数列的代码。让我困惑的是当我们检查 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];
}
最佳答案
由于 fib(i) 应该返回 0 的唯一情况是当 i = 0 时,因此测试 if (memo[i] == 0)
是可以的——它永远不会被调用对于一个值,其中 0 是一个不明确的结果,因为函数的第一行是:if (i == 0
.
请注意,我认为更令人困惑的是为什么在包装器调用中创建内存数组?是的,内存可以节省给定调用的计算量,但在连续调用函数之间所有优化都会丢失。
关于java - Java 中的斐波那契内存/动态编程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43708617/