所谓的斐波纳契数列是指:前两个数是0和1,第i个数是第i-1个数和第i-2个数的和。
eg:斐波纳契数列的钱10 个数是指{0,1,1,2,3,5,8,13,21,34.,,,,,}
一般求解斐波纳契数列的第n个数的值可以用简单的递归来做,代码如下:
public class Solution {public static void main(String[] args){System.out.println(fibonacci(10)); }static int fibonacci(int n){if(n==1) return 0;else{if(n==2) return 1;else{return fibonacci(n-1)+fibonacci(n-2);}}}}
递归的时间复杂度往往都会很高,因此可以用一种可以替代递归的方法---循环,代码如下:
public class Solution {public static void main(String[] args){System.out.println(fibonacci(10)); }static int fibonacci(int n){int[] sum=new int[n];sum[0]=0;sum[1]=1;if(n==1) return sum[0];else{if(n==2) return sum[1];else{for(int i =2;i<n;i++){sum[i]=sum[i-1]+sum[i-2];}return sum[n-1];}}}}