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

n<=39

代码：

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         if( n == 0 )
 5             return 0;
 6         else if ( n == 1 || n == 2)
 7             return 1;
 8         else if ( n == 3)
 9             return 2;
10         else
11             return 3* Fibonacci(n - 3) + 2* Fibonacci(n - 4);
12     }
13 };

我的笔记：该题采用了矩阵快速幂的方法求解，详解参见本人另一篇随笔：https://www.cnblogs.com/john1015/p/12909898.html