题目

官方链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

题解

斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1) ，生成第 n 项的做法有以下几种

1. 递归
   原理：将问题拆分成f(n-1),f(n-2)两个子问题递归，以f(0)=0,f(1)=1为终止条件。
   缺点：会计算大量重复的子问题，f(n)和f(n-1)都要计算f(n-2)的值，例如f(5)和f(4)都要计算f(3)的值。
   AC代码：

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

2. 记忆递归
   原理：就是加一个额外数组，每次递归运算时将计算子问题出来的值存起来，当再遇到这个子问题时直接从数组里面取，这样就避免了重复计算子问题。
   缺点：需要开销O(N)的额外空间。

class Solution {
	private int[] arr = new int[101];

    public int fib2(int n) {
        if (n == 0){
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (arr[n] != 0){
            return arr[n]%1000000007;
        }
        return (fib2(n - 1) + fib2(n-2))%1000000007;
    }
}

3. 动态规划
   原理：以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)f(n+1)=f(n)+f(n−1) 为转移方程。
   从计算效率、空间复杂度上看，动态规划是本题的最佳解法。

		public int fib(int n) {
	        if (n == 0){
	            return 0;
	        }
	        int a = 0;
	        int b = 1;
	        int c = 1;
	        for (int i = 1; i < n; i++) {
	            c = (a + b)%1000000007;
	            a = b;
	            b = c;
	        }
	        return c%1000000007;
 	   }