使用动态规划求解斐波那契数列

自顶向下的动态规划方法结合了递归和记忆化技术。在递归的过程中，我们通过一个数组或哈希表来存储已经计算过的结果，避免了重复计算。

以下是 C 语言的实现：

#include <stdio.h>
#define MAX 1000

int memo[MAX];

// 初始化 memo 数组
void initialize_memo() {
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }
}

// 使用记忆化递归计算斐波那契数列
int fibonacci_memo(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n]; // 返回已经计算过的结果
    }
    // 否则，计算并保存结果
    memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    initialize_memo(); // 初始化 memo 数组
    printf("Fibonacci(%d) = %d\n", n, fibonacci_memo(n));
    return 0;
}

代码分析：

• 在这个实现中，我们使用了一个名为 memo 的数组来保存计算过的斐波那契数值。每次计算 fibonacci_memo(n) 时，首先检查 memo[n] 是否已经有值，如果有值，则直接返回结果；如果没有值，则计算并保存结果。
• 这样做的时间复杂度为 O(n)，空间复杂度为 O(n)。

自底向上的迭代法

在进一步优化中，我们可以将自顶向下的递归方法转换为自底向上的迭代方法，这不仅减少了递归调用的开销，还可以进一步优化空间复杂度。

在计算斐波那契数列时，我们只需要记住前两个数，而不需要存储整个序列。

以下是实现代码：

#include <stdio.h>

// 自底向上的迭代法
int fibonacci_bottom_up(int n) {
    if (n <= 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacci_bottom_up(n));
    return 0;
}

代码分析：

在这段代码中，我们从最小的两个数 0 和 1 开始，通过迭代逐步计算出更大的斐波那契数。我们仅用两个变量 a 和 b 来存储前两个数，从而使得空间复杂度降到了 O(1)。

性能分析与比较

通过对比不同方法的时间复杂度和空间复杂度，我们可以清楚地看到动态规划方法的优势。

从表中可以看到，自底向上的迭代法在时间和空间复杂度上都具有最优性能。

它不仅避免了递归调用的栈空间开销，还通过迭代方法有效降低了空间需求。

小结

斐波那契数列，作为数学中的一颗璀璨明珠，在计算机科学中具有举足轻重的地位。它不仅教会我们递归的基本思想，更让我们意识到优化的重要性。通过动态规划，我们能够以一种高效、优雅的方式解决斐波那契问题，避免了递归方法中冗余计算的困扰。