斐波那契数列【Java版】
斐波那契数列
http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
大家都知道斐波那契数列,现在要求输入一个整数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)【不包括系统栈空间】
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》