一、问题描述

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。即：

F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), 对于 n > 1.

给定 n，计算 F(n)。

二、方案一：递归

1、思路

递归是一种直接的方法，它直接遵循斐波那契数的定义。对于 n > 1，F(n) = F(n - 1) + F(n - 2)。递归的基本情况是 F(0) = 0 和 F(1) = 1。

2、代码实现

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

3、复杂度分析

• 时间复杂度：O(2^n)，因为每个函数调用都会生成两个新的函数调用，形成一棵递归树。
• 空间复杂度：O(n)，因为递归树的深度可以达到 n。

三、方案二：动态规划

1、思路

动态规划方法通过存储已经计算过的斐波那契数来避免重复计算，从而提高效率。我们可以使用一个数组或哈希表来存储这些值。

2、代码实现

func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

3、复杂度分析

• 时间复杂度：O(n)，因为每个数字只计算一次。
• 空间复杂度：O(n)，因为我们需要一个数组来存储 n+1 个斐波那契数。

四、方案三：动态规划（空间优化）

1、思路

在动态规划的基础上，我们可以观察到，计算 F(n) 只需要 F(n-1) 和 F(n-2) 的值。因此，我们不需要存储整个数组，只需要存储前两个斐波那契数。

2、代码实现

func fib(n int) int {
    if n <= 1 {
        return n
    }
    prev, curr := 0, 1
    for i := 2; i <= n; i++ {
        next := prev + curr
        prev, curr = curr, next
    }
    return curr
}

3、复杂度分析

• 时间复杂度：O(n)，因为每个数字只计算一次。
• 空间复杂度：O(1)，因为我们只需要常数级别的额外空间来存储前两个斐波那契数。

五、总结

递归方法虽然直观，但效率低下，特别是对于较大的 n。动态规划方法通过存储已经计算过的值来提高效率。进一步的空间优化可以将空间复杂度降低到常数级别。因此，对于这个问题，推荐使用动态规划的空间优化版本。