【解题报告】斐波拉切数列Fibonacci

题目地址

http://www.lintcode.com/en/problem/fibonacci/

题目大意

给定n，求斐波拉切数列的第n项

思路和解法

主流的思路有两种

1.使用递归来进行求解

该方法非常简单粗暴，直接依照斐波拉切数列的性质使用递归来求解，下面是代码

  public int fibonacci(int n) {
        // write your code here
        return fb(n-1);
    }
    private int fb(int n){
        
        if(n == 0||n == 1){
        return n;
        }
        else
        return fb(n-1)+fb(n-2);
    }

但是该方法有一个问题，当n太大的时候，由于递归层次过多，会超时 ###２.首先暴力打表，然后直接返回第n个 该方法的思想是首先生成前n个，存入数组，这样就不会超时了 代码：

  public int fibonacci(int n) {
        // write your code here
        return fb(n-1);
    }
    private int fb(int n){
        
        if(n == 0||n == 1){
        return n;
        }
        else
        return fb(n-1)+fb(n-2);
    }

总结

对于某些题目，如果正常手段无法奏效，无妨试试特殊手段，比如暴力打表，往往有意想不到的收获，做题时要放宽思路，大胆假设，小心实践。