dynamic-programming - 斐波那契记忆执行顺序

Question

以下代码是使用记忆化的斐波那契数列。但我不明白算法中的执行顺序。如果我们做dynamic_fib(4)，它将计算dynamic_fib(3) + dynamic_fib(2)。左侧先调用，然后计算dynamic_fib(2) + dynamic_fib(1)。但是在计算 dynamic_fib(3) 时，当我们没有像 C 中的 &dic[n] 一样将结果保存到字典的内存地址时，dynamic_fib(2) 的缓存答案如何传播以被重用。

我认为应该发生的是，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-programmingfibonaccimemoization

Answer 1

该函数dynamic_fib（调用一次）只是将工作委托给fibonacci，在那里完成真正的工作。在fibonacci你有一个字典dic，它用于在计算后保存函数的值。所以，当你第一次调用函数时，对于每个值（2-n）fibonacci，它都会计算结果，但它也会将它存储在字典中，这样当我们下次请求它时，我们已经有了它，我们不需要再次遍历整棵树。所以复杂度是线性的，O(n)。