斐波那契数(Java)

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

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

给你 n ,请计算 F(n) 。

解题思路

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

  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;
    }
}
时间复杂度:O(N)
空间复杂度:O(1)
上一篇:golang 树结构化


下一篇:343. 整数拆分 | 暴力求解 | 暴力递归 | 动态规划 | 自顶向下分析