剑指offer_【7】斐波那契数组

1.题目描述

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

• 斐波那契数列：1 1 2 3 5 8 13 21 34 ….

2.解题思路

• 斐波那契数列：从第三项开始，每一项都等于前两项之和。通项公式为

  F(n) = F(n-1)+F(n-2),n>=3
  

方法1：通过递归实现，但是时间复杂度和空间复杂度都会很大

方法2：依次F(n-1)和F(n-2)值，求F(n)就很简单啦

3.代码

方法一：

public class Solution {
    public int Fibonacci(int n) {
        if(n==0)
            return 0;
        else if(n==1 || n==2)
            return 1;
        else
         return (Fibonacci(n-1)+Fibonacci(n-2));   

   }
}

方法2：

public class Solution {
    public int Fibonacci(int n) {
        if (n==0)
            return 0;
        if(n==1||n==2)
            return 1;
        int one_ = 1;  //用于存储f(n-2)

        int two_ =1;   //用于存储f(n-1)

        int fin = 0;
        for(int i = 3;i<=n;i++){
             fin = one_+two_;
             //向前递推

             one_ = two_;   //下一次的f(n-2)为 上一次结果的f(n-1)

             two_ = fin;    //下一次的f(n-1)为 上一次结果的fin 

        }
        return fin;
    }
}