斐波那契（Fibonacci）数列
题目来源
斐波那契（Fibonacci）数列是经典的递推关系式定义的数列。
第一项是0，第二项是1，之后的每一项都是前面两项之和。
POJ3070：
九度剑指Offer：
递归的方法：低效
用递归的方法解斐波那契数列的第n项的值是很直观的做法，因为斐波那契数列的定义就是这种递推的形式。
//用递归的方法求解Fibonacci数列int Fibonacci(int n){ if(n <= 0) { return 0; } else if (n == 1) { return 1; } else { return Fibonacci(n - 1) + Fibonacci(n - 2); }}
但是，递归的方法不是一种很好的解法，有很严重的效率问题。
比如，计算F[5]，需要计算F[4]和F[3]，而计算F[4]的时候又要计算F[3]，所以存在很多结点的重复计算。
像是一颗二叉树，父结点为左右结点之和，那么为了求根节点上的F[n]，就要求它的左右结点F[n-1]和 F[n-2]，而这两个结点的求法和根节点相同，这样扩展下去，当n较大时，计算量会急剧增大。
递推关系式的优化：保存数列中间项，避免重复计算
为了减少重复的计算，可以用一个数组储存所有已计算过的项。
这样便可以达到用空间换取时间的目的。
在这种情况下，时间复杂度为O(n)，而空间复杂度也为O(n)。
这样做的好处在需要多次计算f(n)时更加有利。
比如已经计算过了f(100)，那么就表明f(100)之前的结果都已经计算出来并保存了，第二次想要计算f(50)时，直接查询即可得到。
代码如下，在九度上提交AC（）。
#include "stdafx.h"#includeusing namespace std;int Fibonacci(int n);int main(int argc, char* argv[]){ int n = 0; long fibonacci[1000]; int count = 0;//保存数列已经计算了多少 //先设定起始条件 fibonacci[0] = 0; fibonacci[1] = 1; count = 1; while(cin>>n) { //递归算法 //cout << Fibonacci(n) << endl; //非递归算法 //因为要多次计算f(n)，所以保存这个数列可进一步提高效率 if(n > count) { for(int i = count + 1; i <= n; ++i) { fibonacci[i] = fibonacci[i-1] + fibonacci[i-2]; } cout << fibonacci[n] << endl; } else { //如果n小于等于count，则表明f(n)已经计算出来并且存储在相应的位置上了 cout << fibonacci[n] << endl; } } return 0;}//用递归的方法求解Fibonacci数列int Fibonacci(int n){ if(n <= 0) { return 0; } else if (n == 1) { return 1; } else { return Fibonacci(n - 1) + Fibonacci(n - 2); }}
需要注意的是，开始的时候我用的是int类型数组，所以总是无法通过，因为测试用例的数字已经超过了整形的表示范围。
其他优化方法
《编程之美》中还提到了其他优化方法：
求解通项公式；
使用分治策略，求解矩阵的方幂。
参考资料
《剑指Offer》
《编程之美》
Online Judge:
POJ3070：
九度剑指Offer：
相关解答博客：