【动态规划入门】力扣509题：斐波那契数列的经典解法与优化思路

一、题目解读‌
斐波那契数列是一个经典的数学问题，在计算机科学中常被用作算法教学的入门案例。这个神奇的数列从0和1开始，后续每个数字都是前两个数字之和。题目要求我们计算第n个斐波那契数，看似简单的问题背后却蕴含着重要的算法思想。当n较小时，这个问题似乎微不足道，但随着n的增大，不同的解法在效率上会呈现出天壤之别。

二、解题思路‌
这段代码采用了动态规划的经典解法。首先初始化一个数组来存储计算结果，将前两个斐波那契数f[0]和f[1]分别设为0和1。然后通过一个简单的循环，从第三个数字开始，每个位置的数值都等于前两个位置数值之和，这样逐步构建出整个斐波那契数列。这种方法避免了递归带来的重复计算问题，将时间复杂度从指数级降低到了线性级，是一种典型的空间换时间策略。

三、代码注释

C++

class Solution {
public:
    int fib(int n) {
        int f[100]; // 预分配足够大的数组存储斐波那契数列
        f[0]=0; // 初始化第0项
        f[1]=1; // 初始化第1项
        // 递推计算从第2项到第n项的斐波那契数
        
        for(int i=2;i<=n;i++)
        {
            f[i]=f[i-1]+f[i-2]; // 当前项等于前两项之和
        }
        return f[n]; // 返回第n项结果
    }
};

来源：动态规划入门