7：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

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

上面这个时间好像超过了一秒哎800ms

    public static int getNum(int n){if(n==0){return 0;}else if(n==1){return 1;}else{int arr[] = new int[n+1];arr[0]=0;arr[1]=1;for(int i=2;i<=n;i++){arr[i]=arr[i-1]+arr[i-2];}return arr[n];}}

借助数组空间换时间，10ms