解题思路

如果用递归会超时，所以改用数组存，或者直接输出，代码如下

 

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项

代码实现

1 import java.util.Scanner; 2 public class Solution { 3     public int Fibonacci(int n) { 4         int first = 0; 5         int last = 1; 6         int temp = 0; 7         if(n == 0) 8             return first; 9         if(n == 1)10             return last;11         for(int i = 2; i <= n; i++){12             temp=first+last;13             first = last;14             last = temp;15         }16         return last;17     }18     19     public static void main(String[] args){20         Scanner scanner = new Scanner(System.in);21         Solution solution = new Solution();22         int x = scanner.nextInt();23         System.out.println(solution.Fibonacci(x));24     }25 }

 

用数组实现

1 public class Solution { 2     /* 3      * @param n: an integer 4      * @return: an ineger f(n) 5      */ 6         int[] a = new int[50]; 7     public int fibonacci(int n) { 8          9         if(n<=2)10         return n-1;11         if(a[n]!=0)12         return a[n];13         else14         return a[n]=fibonacci(n-1)+fibonacci(n-2);15     }16 }