链接：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=117&&tqId=34987&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

这是一道比较经典的题目，主要考察的就是递归概念，用前两个数字得到第三个数字即第一个数字 + 第二个数字 = 第三个数字，第二个数字 + 第三个数字 = 第四个数字 依次递推，只要明白其中原理即可。

class Solution {
public:
int Fibonacci(int n) {

 if (n == 1 || n == 2) return 1;//1、1、2、3、5、8、13、21、34
  if (n == 3) return 2;
 vector<int> F(3);
 F[0] = 1;
 F[1] = 1;
 F[2] = 2;
 for (int i = 3; i < n; ++i) {
  F[i % 3] = F[(i - 1) % 3] + F[(i - 2) % 3];


 }
 return F[(n - 1) % 3];

    }
};