写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
通俗的讲，它就是第三个数，等于前两个数之和。
题目
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
解题
动态规划解析：
状态定义： 设 dp为一维数组，其中 dp[i]] 的值代表 斐波那契数列第 ii 个数字 。转移方程： dp[i + 1] = dp[i] +dp[i−1] ，即对应数列定义 f(n + 1) = f(n)+f(n−1)；初始状态： dp[0] = 0, dp[1] = 1，即初始化前两个数字；返回值： dp[n] ，即斐波那契数列的第 n 个数字。
定义三个数分别代表：sum代表f(n+1)，x代表f(n-1)，y代表f(n)
因为f(0)=1 f(1)=1这两个是特殊情况初始化的，n是个数，所以n要从2开始循环遍历
class Solution {public int fib(int n) {int x =0 ;int y =1 ;int sum = 0;if(n==1){return 1;~~删除线格式~~ }else if(n==2){return 1;}for(int i =2; i<=n ;i++){//最低从2开始sum = (x+y)%1000000007;x=y;y=sum;}return sum;}}
官方解答
省略了if判断，直接返回a；
class Solution {public int fib(int n) {int a = 0, b = 1, sum;for(int i = 0; i < n; i++){sum = (a + b) % 1000000007;a = b;b = sum;}return a;}}
