斐波那契数列【Java版】

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

public class Solution {
    public int Fibonacci(int n) {
        int[] fi=new int[40];//设置数组记录中间结果，不然重复计算太多   //根据题目，放心设置数组大小     
        fi[0]=0;fi[1]=1;
        for(int i=2;i<=n;i++){
            fi[i]=fi[i-1]+fi[i-2];
        }
        return fi[n];
    }
}
//动态规划，时间复杂度O(N),空间复杂度O(N)
//如果用递归，时间复杂度O(1.618^N)【上网查的，略小于2^N】,空间复杂度O(1)【不包括系统栈空间】