题目描述
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从 0 开始，第 0 项为 0。
数据范围
0≤n≤39
样例
输入整数 n=5 返回 5
方法一：递推 O(n)
我们可以只用常数个变量来进行计算，具体思路如下：
初始化 a=0 和 b=1 ，如果 n=0 则直接返回 a=0 。
如果 n>0 则计算 c=a+b ，然后将 a 和 b 往后移一位即 a=b,b=c 。
来看个例子加深一下印象，假设传入参数 n 为 4 ：
第一步： 初始化变量 a=0,b=1 。
第二步： 开始循环，计算 c=a+b=1 ，a 更新为 b ，b 更新为 c ，并且 n 要减 1 。
第三步 ~ 第五步： 和第二步一样，类似于是一个滚动数组，一直往后面移动。
第六步： 直到 n 为 0 ，返回 a 就是最终的答案。
class Solution { public: int Fibonacci(int n) { int a = 0, b = 1; while (n--) { int c = a + b; a = b, b = c; } return a; } };
欢迎大家在评论区交流~
