斐波纳契数

Fibonacci 数是动态规划的主要主题，因为传统的递归方法会进行大量的重复计算。在这些例子中，我将使用 f(0) = f(1) = 1 的基本情况。

这是 fibonacci(4) 的示例递归树，请注意重复的计算： https://i.stack.imgur.com/CLwKE.jpg

非动态编程 O(2^n) 运行时复杂度，O(n) 堆栈复杂度

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

这是编写问题最直观的方法。当你下降第一个递归分支来调用 fibonacci(n-1) 直到你击中基本情况 n < 2 时，最多堆栈空间将是 O(n)。

这里可以看到 O(2^n) 运行时复杂性证明： Fibonacci 序列的计算复杂性 。要注意的要点是运行时是指数的，这意味着每个后续项的运行时间将加倍，fibonacci(15) 将是 fibonacci(14) 的两倍。

memoized O(n) 运行时复杂度，O(n) 空间复杂度，O(n) 堆栈复杂度

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

通过 memoized 方法，我们引入了一个可以被认为是所有先前函数调用的数组。memo[n] 的位置是函数调用 fibonacci(n) 的结果。这允许我们为 O(n) 运行时交换 O(n) 的空间复杂度，因为我们不再需要计算重复的函数调用。

迭代动态编程 O(n) 运行时复杂度，O(n) 空间复杂度，无递归堆栈

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

如果我们将问题分解为它的核心元素，你会注意到为了计算 fibonacci(n)，我们需要 fibonacci(n-1) 和 fibonacci(n-2)。我们还注意到，我们的基本情况将出现在递归树的末尾，如上所示。

有了这些信息，现在有必要向后计算解决方案，从基础案例开始向上计算。现在为了计算 fibonacci(n)，我们首先计算到 n 之前的所有斐波纳契数。

这里的主要好处是我们现在已经消除了递归堆栈，同时保持了 O(n) 运行时。不幸的是，我们仍然有一个复杂的空间复杂性，但也可以改变。

高级迭代动态编程 O(n) 运行时复杂度，O(1) 空间复杂度，无递归堆栈

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

如上所述，迭代动态编程方法从基本情况开始并且工作到最终结果。为了使空间复杂度达到 O(1)（常数）所做的关键观察是我们为递归堆栈做的相同观察 - 我们只需要 fibonacci(n-1) 和 fibonacci(n-2) 来构建 fibonacci(n)。这意味着我们只需要在迭代中的任何一点保存 fibonacci(n-1) 和 fibonacci(n-2) 的结果。

为了存储这最后两个结果，我使用一个大小为 2 的数组，并简单地使用 i % 2 翻转我指定的索引，i % 2 将交替使用：0, 1, 0, 1, 0, 1, ..., i % 2。

我将数组的两个索引一起添加，因为我们知道添加是可交换的（5 + 6 = 11 和 6 + 5 == 11）。然后将结果分配给两个点中的较旧点（由 i % 2 表示）。然后将最终结果存储在 n%2 位置

笔记

• 重要的是要注意，有时最好为重复执行大型计算的函数提出迭代的 memoized 解决方案，因为你将建立一个函数调用的答案缓存，如果已经有后续调用可能是 O(1) 已被计算。