【剑指offer-09】斐波那契数列

题目描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

题目解析

【分析】 1、最常用的解法就是递归调用，先定义结束条件n<=0时返回1，n=1时返回1，然后计算fib(n-1)+fib(n-2)，会出现很多重复调用，当输入的数比较大时计算很慢（在leetcode上面会超时） 2、从下往上利用循环计算，先根据fib(0)、fib(1)计算出fib(2)，再根据fib(1)、fib(2)计算出fib(3)，依次类推可以算出第n项，除以1000000007保证在最大整数返回内，即不会越界 【代码实现】

public int fib(int n) { int constant = 1000000007; int fibZero = 0; int fibOne = 1; while (n-->0){ int temp = fibZero + fibOne; fibZero = fibOne % constant; fibOne = temp % constant; } return fibZero; }