题目：大家都知道斐波那契数列，现在要求输入一个整数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
原文：https://www.cnblogs.com/john1015/p/12909907.html