斐波那契数列

题目链接

牛客网

题目描述

求斐波那契数列的第 n 项，n <= 39。

解题思路

如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。

递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。

java

1public int Fibonacci(int n) {
2    if (n <= 1)
3        return n;
4    int[] fib = new int[n + 1];
5    fib[1] = 1;
6    for (int i = 2; i <= n; i++)
7        fib[i] = fib[i - 1] + fib[i - 2];
8    return fib[n];
9}

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

java

1public int Fibonacci(int n) {
2    if (n <= 1)
3        return n;
4    int pre2 = 0, pre1 = 1;
5    int fib = 0;
6    for (int i = 2; i <= n; i++) {
7        fib = pre2 + pre1;
8        pre2 = pre1;
9        pre1 = fib;
10    }
11    return fib;
12}

由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值。

java

1public class Solution {
2
3    private int[] fib = new int[40];
4
5    public Solution() {
6        fib[1] = 1;
7        for (int i = 2; i < fib.length; i++)
8            fib[i] = fib[i - 1] + fib[i - 2];
9    }
10
11    public int Fibonacci(int n) {
12        return fib[n];
13    }
14}

📝 转载声明

本文转载自开源项目 CS-Notes，原作者为 CyC2018。

原文链接：10.1 斐波那契数列

版权声明：本文章遵循 MIT 协议。您可以自由复制、分发，但必须保留原作者署名。

内容概要：技术面试中斐波那契数列的经典解法与空间复杂度优化。

斐波那契数列

题目链接

题目描述

解题思路

📝 转载声明

评论区