执行斐波那契记忆顺序
Fibonacci memoization order of execution
以下代码是使用记忆的斐波那契数列。但是我不明白算法中的执行顺序。如果我们执行 dynamic_fib(4)，它将计算 dynamic_fib(3) + dynamic_fib(2)。左边先调用，然后计算 dynamic_fib(2) + dynamic_fib(1)。但是在计算 dynamic_fib(3) 时，当我们没有像 &dic[n] 那样将结果保存到字典的内存地址时，dynamic_fib(2) 的缓存答案如何向上传播以供重用在 C.
我认为应该发生的是 dynamic_fib(2) 的答案消失了，因为它只存在于那个堆栈中。所以在计算dynamic_fib(4)
的时候还要再计算一次dynamic_fib(2)
我是不是漏掉了什么？
def dynamic_fib(n):
return fibonacci(n, {})
def fibonacci(n, dic):
if n == 0 or n == 1:
return n
if not dic.get(n, False):
dic[n] = fibonacci(n-1, dic) + fibonacci(n-2, dic)
return dic[n]
函数dynamic_fib（调用一次）只是将工作委托给fibonacci，真正的工作在那里完成。在 fibonacci 中，您有字典 dic，它用于在计算后保存函数的值。所以，对于（2-n）中的每一个值，当你第一次调用函数fibonacci时，它会计算结果，但它也会将其存储在字典中，以便下次我们请求时它，我们已经有了它，我们不需要再次遍历整棵树。所以复杂度是线性的，O(n)。
以下代码是使用记忆的斐波那契数列。但是我不明白算法中的执行顺序。如果我们执行 dynamic_fib(4)，它将计算 dynamic_fib(3) + dynamic_fib(2)。左边先调用，然后计算 dynamic_fib(2) + dynamic_fib(1)。但是在计算 dynamic_fib(3) 时，当我们没有像 &dic[n] 那样将结果保存到字典的内存地址时，dynamic_fib(2) 的缓存答案如何向上传播以供重用在 C.
我认为应该发生的是 dynamic_fib(2) 的答案消失了，因为它只存在于那个堆栈中。所以在计算dynamic_fib(4)
的时候还要再计算一次dynamic_fib(2)我是不是漏掉了什么？
def dynamic_fib(n):
return fibonacci(n, {})
def fibonacci(n, dic):
if n == 0 or n == 1:
return n
if not dic.get(n, False):
dic[n] = fibonacci(n-1, dic) + fibonacci(n-2, dic)
return dic[n]
函数dynamic_fib（调用一次）只是将工作委托给fibonacci，真正的工作在那里完成。在 fibonacci 中，您有字典 dic，它用于在计算后保存函数的值。所以，对于（2-n）中的每一个值，当你第一次调用函数fibonacci时，它会计算结果，但它也会将其存储在字典中，以便下次我们请求时它，我们已经有了它，我们不需要再次遍历整棵树。所以复杂度是线性的，O(n)。