引言
斐波那契数列，这一数列如同一条无形的丝线，穿越千年时光，悄然延续其魅力。其定义简单而优美：
F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2), n>1
这看似简单的递归公式，却蕴含着深刻的数学结构，成为计算机科学中的经典问题之一。斐波那契数列不仅仅出现在数学课本上，它在自然界、计算机算法、金融模型等领域中无处不在。对于程序员而言，斐波那契数列不仅是一个练习递归的好题目，更是一个优化算法的标杆。
在这篇文章中，我们将通过动态规划的技术来探讨如何高效地求解斐波那契数列，从而避免传统递归方法中低效的冗余计算。我们将以 C 语言为例，展示动态规划方法如何一步步揭开这一问题的面纱。
递归与动态规划的对比
递归解法的初探
初识斐波那契数列，往往从递归开始。递归是一个从问题的定义出发，层层拆解的过程。我们通过编写递归函数来模拟斐波那契数列的计算：
#include <stdio.h>
int fibonacci_recursive(int n) {
if (n <= 1) {
return n;
}
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}
int main() {
int n = 10;
printf("Fibonacci(%d) = %d\n", n, fibonacci_recursive(n));
return 0;
}
代码分析：
这段代码极其直观，正如数列的定义那样，利用递归直接表达了斐波那契数列的生成。
然而，这种实现方式的效率极低。
- 对于每一个
fibonacci_recursive(n)调用，都会同时递归调用fibonacci_recursive(n-1)和fibonacci_recursive(n-2)，造成了大量的重复计算。例如，在计算fibonacci_recursive(5)时，会重复计算fibonacci_recursive(3)和fibonacci_recursive(2)。 - 通过这样的计算树可以看到，随着 n 值的增加，重复计算的次数呈指数级增长。时间复杂度为 O(2^n)，这对于较大的 n 来说，已经无法接受。
动态规划的优雅与高效
递归方法的瓶颈在于大量的重复计算，而动态规划（Dynamic Programming, DP）正是为了解决这个问题而应运而生。
动态规划的精髓在于通过存储中间结果来避免重复计算，将复杂的递归结构转化为迭代计算。
动态规划解决斐波那契数列问题的关键在于，子问题之间是重叠的，即在计算 F(n) 时，F(n-1) 和 F(n-2) 都已经被计算过，因此可以将这些中间结果保留，从而提高效率。
