题解 | #斐波那契数列#

题目主要信息

• 斐波那契数列公式为:$F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+F(n-2)$
• 初始化第1项和第2项为1
• 求该数列第n项

举一反三：

学习完本题的思路你可以解决如下题目：

BM63.跳台阶

BM64.最小花费爬楼梯

BM69.把数字翻译成字符串

方法一：迭代相加（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

思路：

斐波那契数列初始化第1项与第2项都是1，则根据公式第0项为0，可以按照斐波那契公式累加到第$nn$项。

具体做法：

• step 1：低于2项的数列，直接返回n。
• step 2：初始化第0项，与第1项分别为0，1.
• step 3：从第2项开始，逐渐按照公式累加，并更新相加数始终为下一项的前两项。

Java实现代码：

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n <= 1)    
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         //因n=2时也为1，初始化的时候把a=0，b=1
         for (int i = 2; i <= n; i++){
         //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n <= 1)    
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         //因n=2时也为1，初始化的时候把a=0，b=1
         for (int i = 2; i <= n; i++){
         //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
};

Python代码实现：

class Solution:
    def Fibonacci(self , n: int) -> int:
        #从0开始，第0项是0，第一项是1
        if n <= 1:    
            return n
        res = 0
        a = 0
        b = 1
        #因n=2时也为1，初始化的时候把a=0，b=1
        for i in range(2, n + 1): 
        #第三项开始是前两项的和,然后保留最新的两项，更新数据相加
            res = (a + b)
            a = b
            b = res
        return res

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为输入的数，$nn$次迭代
• 空间复杂度：$O(1)O(1)$，常数级变量，没有其他额外辅助空间

方法二：递归法（扩展思路）

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

思路：

我们也可以根据公式倒推，因为$F(n)=F(n-1)+F(n-2)F(n)=F(n-1)+F(n-2)$，而$F(n-1)F(n-1)$与$F(n-2)F(n-2)$又可以作为子问题继续计算，因此可以使用递归。

• 终止条件： 当递归到数列第1项或是第0项的时候，可以直接返回数字。
• 返回值： 返回这一级子问题的数列值。
• 本级任务： 获取本级数列值：即前两项相加。

具体做法：

• step 1：低于2项的数列，直接返回n。
• step 2：对于当前n，递归调用函数计算两个子问题相加。

Java实现代码：

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if (n <= 1)    
             return n;
        else{
            //根据公式递归调用函数
            return Fibonacci(n - 1) + Fibonacci(n - 2); 
        }
    }
}

C++实现代码：

class Solution {
public:
    int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if (n <= 1)    
             return n;
        else{
            //根据公式递归调用函数
            return Fibonacci(n - 1) + Fibonacci(n - 2); 
        }
        return 0;
    }
};

Python代码实现：（利用数组存储递归值，优化时间）

class Solution:
    def __init__(self):
        self.num = [0 for i in range(41)]
    def Fibonacci(self , n: int) -> int:
        #从0开始，第0项是0，第一项是1
        if n <= 1:    
            self.num[n] = n
            return n
        if self.num[n - 1] == 0:
            self.num[n - 1] = self.Fibonacci(n - 1)
        if self.num[n - 2] == 0:
            self.num[n - 2] = self.Fibonacci(n - 2)
        #根据公式递归调用函数
        return self.num[n - 1] + self.num[n - 2] 

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，每个递归会调用两个递归，因此呈现2的指数增长（Python版本优化为$O(n)O(n)$）
• 空间复杂度：$O(n)O(n)$, 递归栈的最大深度

方法三：动态规划(扩展思路)

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

既然是数列，我们就把它放入数组中来解决，用数组下标表示斐波那契数列的第几项。

具体做法：

• step 1：创建一个长度为$n+1n+1$的数组，因为只有$n+1n+1$才能有下标第$nn$项，我们用它记录前$nn$项斐波那契数列。
• step 2：根据公式，初始化第0项和第1项（题目中是第1项和第2项，本质上一样的）。
• step 3：遍历数组，依照公式某一项等于前两项之和，将数组后续元素补齐，即可得到$fib[n]fib[n]$。

图示：

Java实现代码：

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n <= 1)   
             return n;
        int[] fib = new int[n + 1];
	    fib[0] = 0;
	    fib[1] = 1;
        //依次相加
	    for (int i = 2; i <= n; i++) 
		    fib[i] = fib[i - 1] + fib[i - 2];
	    return fib[n];
    }
}

C++实现代码：

class Solution {
public:
    int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if (n <= 1)    
             return n;
        int* fib = new int[n + 1];
	    fib[0] = 0;
	    fib[1] = 1;
        //依次相加
	    for (int i = 2; i <= n; i++) 
		    fib[i] = fib[i - 1] + fib[i - 2];
	    return fib[n];
    }
};

Python代码实现：

class Solution:
    def Fibonacci(self , n: int) -> int:
        #从0开始，第0项是0，第一项是1
        if n <= 1:    
            return n
        fib = [0 for i in range(n + 1)]
        fib[0] = 0
        fib[1] = 1
        #依次相加
        for i in range(2, n + 1): 
            fib[i] = fib[i - 1] + fib[i - 2]
        return fib[n]

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一个for循环遍历
• 空间复杂度：$O(n)O(n)$，创建了一个大小为$n+1n+1$的动态数组