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

19339201706

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

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

三、代码和注释

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

复制代码

来源：动态规划入门