C#动态规划之斐波那契优化（从递归到高效解法的完整指南）

方法一：朴素递归（效率极低）

很多初学者会直接用递归来实现斐波那契：

public static long FibonacciRecursive(int n){    if (n <= 1)        return n;        return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);}

这种方法看似简洁，但存在严重的性能问题：时间复杂度为 O(2ⁿ)！计算 F(50) 可能需要几分钟甚至更久，因为它重复计算了大量相同的子问题。

方法二：记忆化递归（自顶向下动态规划）

为了解决重复计算的问题，我们可以用一个字典（或数组）来“记住”已经计算过的值，这就是动态规划入门中的“记忆化”技巧：

private static Dictionary<int, long> memo = new Dictionary<int, long>();public static long FibonacciMemo(int n){    if (n <= 1)        return n;        if (memo.ContainsKey(n))        return memo[n];        long result = FibonacciMemo(n - 1) + FibonacciMemo(n - 2);    memo[n] = result;    return result;}

现在时间复杂度降到了 O(n)，空间复杂度也是 O(n)。这是一个巨大的提升！

方法三：迭代法（自底向上动态规划）

更进一步，我们可以完全避免递归，使用循环从 F(0) 和 F(1) 开始，一步步计算到 F(n)。这种方法是典型的C#算法教程中推荐的动态规划写法：

public static long FibonacciIterative(int n){    if (n <= 1)        return n;        long prev2 = 0; // F(0)    long prev1 = 1; // F(1)    long current = 0;        for (int i = 2; i <= n; i++)    {        current = prev1 + prev2;        prev2 = prev1;        prev1 = current;    }        return current;}

这个版本的时间复杂度是 O(n)，空间复杂度仅为 O(1)，是最优解之一！

性能对比

总结

通过斐波那契数列这个例子，我们清晰地看到了C#动态规划如何将一个指数级时间复杂度的问题优化到线性甚至常数空间。掌握这种“避免重复计算”的思想，是学习更复杂动态规划问题（如背包问题、最长公共子序列等）的基础。

希望这篇C#算法教程能帮助你理解斐波那契数列优化的核心思路，并顺利迈入动态规划入门的大门！动手试试吧，你会发现算法其实很有趣！