斐波那契数列的四种实现算法

人不走空

发布于 2024-03-23 09:40:28

1130

发布于 2024-03-23 09:40:28

文章被收录于专栏：学习与分享学习与分享

斐波那契数列（Fibonacci Sequence）是一组自然数序列，其特点是每个数都是前两个数之和。斐波那契数列的起始数字通常为0和1，序列依次为0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...。

虽然斐波那契数列最初是作为数学问题而出现，但它在计算机科学领域中有着广泛的应用。本文将深入探讨斐波那契数列在计算机科学中的几个重要应用，并介绍它们的实现原理及具体案例。

1. 斐波那契数列在动态规划中的应用：

动态规划是一种解决问题的算法设计方法，通过将原问题分解为相互重叠的子问题，并通过保存子问题的解以避免重复计算来提高效率。斐波那契数列是动态规划中一个经典的例子。

在动态规划中，斐波那契数列的第n个数字可以通过以下递推关系计算：

F(n) = F(n-1) + F(n-2)

其中，F(0) = 0，F(1) = 1。通过动态规划的思想，我们可以利用递推关系迭代地计算出斐波那契数列中任意位置的数字，而不必重复计算相同的子问题。

2.解题思路

斐波那契数是一道非常经典的题目，可以使用暴力递归，也可以使用动态规划等方法。本题给出四种解答，分别是

1.代码1 —— 暴力题解

2.代码2 —— 使用带备忘录的递归解法

3.代码3 —— dp数组的动态规划方法

4.代码4 —— 迭代，优化空间复杂度

代码1 —— 暴力题解

class Solution {
    public int fib(int n) {
        // base case
        if (n == 0 || n == 1) {
            return n;
        }
        // 递推关系
        return fib(n - 1) + fib(n - 2);
    }
}

时间复杂度：O(2^N)

空间复杂度：O(1)

代码2 —— 带备忘录的递归解法

class Solution {
    public int fib(int n) {
        // 备忘录全部初始化为0
        int[] memo = new int[n + 1];
        // 进行带备忘录的递归
        return helper(memo, n);
    }

    private int helper(int[] memo, int n) {
        // base case
        if (n == 0 || n == 1) {
            return n;
        }
        // 进行检查，已经计算过就不用在计算了
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}

时间复杂度：O(N)

空间复杂度：O(N)

代码3 —— 使用 dp 数组的动态规划方法

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        // base case
        dp[0] = 0; dp[1] = 1;
        // 状态转移
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

时间复杂度：O(N)

空间复杂度：O(N)

代码4 —— 迭代，优化空间复杂度

class Solution {
    // 优化空间复杂度
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        // 递推关系
        int prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }
}