【每日一题】2020.01.04 509. 斐波那契数

509. 斐波那契数

题目描述:

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

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

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

提示：

0 <= n <= 30

题解1：递归


class Solution {
    public int fib(int n) {
        if(n==1) return 1;
        if(n==0) return 0 ;
        return fib(n-1)+fib(n-2);
    }
}

根据定义写出的递归算法，较直观，无需多言。

1 2	执行用时：9 ms, 在所有 Java 提交中击败了22.00%的用户内存消耗：35.3 MB, 在所有 Java 提交中击败了42.32%的用户

可以看到递归解法时间性能和空间性能很一般，原因在于当递归层数比较深时，递归调用的时间开销很大，递归函数栈所占用的空间也很大。遂尝试使用非递归解法。

题解2：动态规划

在计算斐波那契数时，会有重复的子问题。以计算fib(4)*为例。如下图，计算 *fib(4) 时需要计算fib(3)和fib(2)，或者说fib(4)可以分解为fib(3)和fib(2)两个子问题。而计算fib(3)时，还需再计算一遍fib(2)，即有重复的子问题fib(2)。如果能使用一个数组在计算fib(3)时就把fib(2)的结果记录下来，就可以略去很多不必要的计算，去掉重复子问题。

那么就采用自下而上的、非递归的动态规划算法，并使用数组arr[]存放子问题的解。即先计算fib(0)结果存放至arr[0]，再计算fib(1)存放至arr[1]，再计算fib(2)存放至arr[2]………，最后计算fib(n)，结果存放至arr[n]。

class Solution {
    public int fib(int n) {
        //如果求第0或1个斐波那契数，根据定义，结果自然是0或1直接返回即可
        if(n==0||n==1)return n;
        //使用数组arr存放子问题的解
        int arr[]=new int[n+1];
        arr[0]=0;
        arr[1]=1;
        for(int i=2;i<n+1;i++){
            //计算fib(i)
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
}

1 2	执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗：35.1 MB, 在所有 Java 提交中击败了66.28%的用户

看起来不错，时间性能大大提高，但是空间性能是不是还能提升呢？

题解3 动态规划（空间优化版）

对动态规划版本再进行优化，其实每次需要保存的数字只有2个，即i-1和i-2

class Solution {
    public int fib(int n) {
        if(n==0||n==1)return n;
        int a=0 ,b=1;
        for(int i=2;i<n+1;i++){
            int temp=b; 
            b=a+b;
            a=temp;
        }
        return b;
    }
}

1
2
3

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：35.2 MB, 在所有 Java 提交中击败了65.48%的用户

其他解法

矩阵快速幂和通项公式法可参见官方题解

https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

这两种解法要求有一定的数学基础，有兴趣的同学可自行研究。