【数据结构和算法】4种解决方式，图文详解

1，递归解决

这题非常简单，我们直接按照公式来就可以了F(n) = F(n - 1) + F(n - 2)，但要做好边界条件的判断F(0) = 0，F(1) = 1

    public int Fibonacci(int n) {
        if (n < 2)
            return n;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

之前讲《356，青蛙跳台阶相关问题》的时候也提到过斐波那契数列，斐波那契数列递归的时候会造成大量的重复计算，比如就计算fib(6)为例来看下

我们看到上面相同颜色的都是重复计算，当n越大，重复的越多，所以我们可以使用一个map把计算过的值存起来，每次计算的时候先看map中有没有，如果有就表示计算过，直接从map中取，如果没有就先计算，计算完之后再把结果存到map中。

    public int Fibonacci(int n) {
        return helper(n, new HashMap());
    }

    private int helper(int n, Map<integer, integer> map) {
        if (n &lt; 2)
            return n;
        if (map.containsKey(n))
            return map.get(n);
        int first = helper(n - 1, map);
        int second = helper(n - 2, map);
        int res = (first + second);
        map.put(n, res);
        return res;
    }

2，非递归解法

我们还可以把斐波那契递归改为非递归，代码很简单，可以看下

    public int Fibonacci(int n) {
        int first = 0;
        int second = 1;
        while (n-- > 0) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return first;
    }

3，公式计算

在《356，青蛙跳台阶相关问题》的最后还提到斐波那契数列实际上是有个公式的，

所以我们还可以通过公式来计算。

    public int Fibonacci(int n) {
        double fun1 = (1 + Math.sqrt(5)) / 2;
        double fun2 = (1 - Math.sqrt(5)) / 2;
        return (int) Math.round((Math.pow(fun1, n) - Math.pow(fun2, n)) / Math.sqrt(5));
    }

4，直接查找

因为在int范围内，斐波那契数列的值是有限的，并且也不多，所以可以使用查表的方法解决

    public int Fibonacci(int n) {
        int[] table = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
                4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040
                , 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986};
        return table[n];
    }

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解