10.1 斐波那契数列

题目链接

NowCoder

题目描述

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

解题思路

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

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

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int[] fib = new int[n + 1];
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}

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

public int Fibonacci(int n) {
    if (n <= 1)
        return n;
    int pre2 = 0, pre1 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = pre2 + pre1;
        pre2 = pre1;
        pre1 = fib;
    }
    return fib;
}

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

public class Solution {

    private int[] fib = new int[40];

    public Solution() {
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
    }

    public int Fibonacci(int n) {
        return fib[n];
    }
}

c++实现：

//递归-不采用
class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        else
            return Fibonacci(n-1) + Fibonacci(n - 2);
    }
};
C++ 代码
class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n -- ) {
            int c = a + b;
            a = b, b = c;
        }
        return a;
    }
};
//更好理解
class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0 || n == 1) return n;
        int a = 0, b = 1; //表示n -2 n -1 （第0 1位=0 1）
        int res = 0;
        for(int i = 2; i <= n; i ++)
        {
            res = a + b;  //a b c d =>
            a = b;
            b = res;
        }
        return res;
    }
};

java 实现

class Solution {
    public int fib(int n) {
        if(n<=1) return n;

        int a = 0;
        int b = 1;
        for(int i = 2; i <= n; i ++) {
            int tmp = b;
            b = a + b;
            a = tmp;
            if(b > 1000000007) b %= 1000000007;
        }
        return b;
    }
}