斐波那契数列.md

题目描述

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

##输入描述

一个整数n

##输出描述

斐波那契数列的第n项。

##题目分析

###什么是斐波那契数列？

　　

斐波那契数列（Fibonacci sequence），又称黄金分割数列

在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）　　

指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……　

###递归？

　　看到这个的第一想法就是用递归，当ｎ＜２时返回ｎ，ｎ＞＝２时返回ｆ(n-1)+f(n-2), 于是就来试一下... 　　

public class Solution {
    public int Fibonacci(int n) {
        if(n<2){
            return n;
        }
        
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

为什么呢？

　　因为重复计算，比如：

ｆ(4) = ｆ(3) + ｆ(2);
    　 = ｆ(2) + ｆ(1) + ｆ(1) + ｆ(0);
    　 = ｆ(1) + ｆ(0) + ｆ(1) + ｆ(1) + ｆ(0);

求ｆ(4)就要计算三次ｆ(1)和两次ｆ(0)，显然这是不行的。

解法 (动态规划)

运行时间：27ms 占用内存：629k

public class Solution {
    public int Fibonacci(int n) {
         int i = 0, j = 1;
         for(;n>0;n--){
            j += i;
            i = j-i;
        }
        return i;
    }
}

根据n的大小，从f(0)=i 和 f(1)=j 从头开始遍历整个序列

有f(n)=f(n-1)+f(n-2) （n≥2，n∈N*）

j+=i, 使j成为新的f(n-1)

i = j-i ，使i成为f(n-2)

完成后，返回 f(n-2)

注意：java中

while(n--)

会报编译错误：

required: boolean found: int