509.斐波那契数

LeetCode LeetCode 动态规划数学递归记忆化搜索

发布时间 : 2000-01-10 05:00

字数:1.2k 阅读 :

评论:

509.斐波那契数

509.斐波那契数

509.1 题目

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n，请计算 F(n)。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 30

509.2 题解

方法一：递归

思路

直接按照定义递归：F(n) = F(n-1) + F(n-2)。基准情况是 F(0) = 0，F(1) = 1。简单但存在大量重复计算。

核心思想：直接按定义递归，存在重复计算。

具体步骤：

如果 n <= 1：返回 n
否则：返回 Fib(n-1) + Fib(n-2)

举例：对于 n = 4：

Fib(4) = Fib(3) + Fib(2)
Fib(3) = Fib(2) + Fib(1)
Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1
回溯：Fib(3) = 1 + 1 = 2
Fib(4) = 2 + 1 = 3

复杂度分析

时间复杂度：O(2^n)，指数级递归。
空间复杂度：O(n)，递归栈深度。

代码

// 方法一：递归
static int Fib1(int n)
{
    // 如果 n 小于等于 1，直接返回 n，作为基准情况
    if (n <= 1)
    {
        return n;
    }
    else
    {
        // 递归调用 Fibonacci1 函数，计算 F(n) = F(n-1) + F(n-2)
        return Fib1(n - 1) + Fib1(n - 2);
    }
}

方法二：迭代

思路

使用数组存储已计算的值，从 F(0) 和 F(1) 开始迭代计算到 F(n)。避免了递归的重复计算。

核心思想：自底向上迭代，避免重复计算。

具体步骤：

如果 n <= 1：返回 n
创建数组 dp，dp[0] = 0，dp[1] = 1
从 i = 2 到 n：dp[i] = dp[i-1] + dp[i-2]
返回 dp[n]

举例：对于 n = 4：

dp = [0, 1, ?, ?, ?]
i=2：dp[2] = 0 + 1 = 1
i=3：dp[3] = 1 + 1 = 2
i=4：dp[4] = 2 + 1 = 3
结果：3

复杂度分析

时间复杂度：O(n)，迭代 n 次。
空间复杂度：O(n)，存储数组。

代码

// 方法二：迭代
static int Fib2(int n)
{
    // 如果 n 小于等于 1，直接返回 n，作为基准情况
    if (n <= 1)
    {
        return n;
    }

    // 初始化一个数组 fib 来存储斐波那契数列的结果
    int[] fib = new int[n + 1];
    fib[0] = 0; // F(0) 的初始值为 0
    fib[1] = 1; // F(1) 的初始值为 1

    // 使用循环迭代计算 F(i) = F(i-1) + F(i-2) 的值，将结果存储在数组 fib 中
    for (int i = 2; i <= n; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    // 返回计算结果，即 F(n)
    return fib[n];
}

509.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 斐波那契数列计算
        // 给定 n ，计算 F(n)。

        // 示例 1：
        // 输入：n = 2
        // 输出：1
        // 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

        // 示例 2：
        // 输入：n = 3
        // 输出：2
        // 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

        // 示例 3：
        // 输入：n = 4
        // 输出：3
        // 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

        #endregion

        #region 测试

        // 示例 1
        int n1 = 2;
        int result1 = Fib1(n1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = Fib2(n1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int n2 = 3;
        int result2 = Fib1(n2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = Fib2(n2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int n3 = 4;
        int result3 = Fib1(n3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        int result3_2 = Fib2(n3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归
    static int Fib1(int n)
    {
        // 如果 n 小于等于 1，直接返回 n，作为基准情况
        if (n <= 1)
        {
            return n;
        }
        else
        {
            // 递归调用 Fibonacci1 函数，计算 F(n) = F(n-1) + F(n-2)
            return Fib1(n - 1) + Fib1(n - 2);
        }
    }

    // 方法二：迭代
    static int Fib2(int n)
    {
        // 如果 n 小于等于 1，直接返回 n，作为基准情况
        if (n <= 1)
        {
            return n;
        }

        // 初始化一个数组 fib 来存储斐波那契数列的结果
        int[] fib = new int[n + 1];
        fib[0] = 0; // F(0) 的初始值为 0
        fib[1] = 1; // F(1) 的初始值为 1

        // 使用循环迭代计算 F(i) = F(i-1) + F(i-2) 的值，将结果存储在数组 fib 中
        for (int i = 2; i <= n; i++)
        {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        // 返回计算结果，即 F(n)
        return fib[n];
    }

    #endregion
}

509.4 运行结果

示例1 方法1 输出：1
示例1 方法2 输出：1
示例2 方法1 输出：2
示例2 方法2 输出：2
示例3 方法1 输出：3
示例3 方法2 输出：3

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com