斐波那契数列

题目描述

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

• 斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..
• 这个数列从第3项开始，每一项都等于前两项之和。

解题思路

• f(n) = f(n-1) + f(n-2); f(n-1) = f(n-2) + f(n-3) 初步想法是使用递归，但是这样会有重复计算的问题（f(n-2)重复计算）。
• 由于第n项只与第n-1项与第n-2项有关，所以只计算前两项的结果再重新赋值计算即可。

代码

public class Solution {
    public int Fibonacci(int n) {
        if(n < 1){
            return 0;
        }
        if(n <= 2){
            return 1;
        }
        int sum = 0,a = 0,b = 1,i = 2;
        while(i <= n){
            sum = a + b ;
            a = b;
            b = sum;
            i++;
        }
        return sum;
    }
}