斐波那契数列（Fibonacci sequence）指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、55、89、144、……
在数学上，斐波那契数列的方法定义：
f(0) = 0
f(1) = 1
f(n) = f(n - 1) f(n - 2)（n ≥ 2）
这个数列从第3项开始，每一项都等于前两项之和。
方法1：递归递归实现：
int fRecursion(int n){
if (n == 0) return 0;
if (n == 1) return 1;
return fRecursion(n - 1) fRecursion(n - 2);
}
时间复杂度: O(2ⁿ)
我们用下面的递归调用树来理解递归实现的时间复杂度：
图1
因为每个节点在递归调用之外的工作时间为O(1), 所以运行时间等于调用的次数，即树中节点的总数。
这棵树有多少节点呢？假设我们要计算f(n), 根据图1我们可以知道树的深度为(n - 1)。
如果这是一棵完全二叉树，则树的总节点数为(2ⁿ-1)，因此时间复杂度为O(2ⁿ)。
通过观察图1，我们可以看到右子树节点数总是比左子树节点数少，因此这棵树的总节点数比同样深度的完全二叉树少（真实运行时间接近O(1.6ⁿ))。因为O(2ⁿ)描述的是运行时间的上界，我们可以简单地说递归实现的时间复杂度为 O(2ⁿ)。
方法2：自上而下的动态规划通过观察图1，我们可以看到很多重复的节点。其中f(3)出现了2次，f(2)出现了3次。为什么要重复地计算f(3), f(2)......? 如果我们把计算过的f(i)的值缓存起来，下次遇到计算过的值直接从缓存里取。递归过程如下图（灰色圆圈的值从缓存取）：
图2
根据图2，我们可以看到f(n)的调用次数不超过O(n)。
自上而下的动态规划实现：
int fDynamicUpDown(int n){
return fDynamicUpDown(n, new int[n 1]);
}
int fDynamicUpDown(int i, int[] num) {
if (i == 0) return 0;
if (i == 1) return 1;
if(num[i] == 0){
num[i] = fDynamicUpDown(i - 1, num) fDynamicUpDown(i - 2, num);
}
return num[i];
}
时间复杂度: O(n)
方法3：自下而上的动态规划从已知条件中已经知道f(1)和f(0)的值，通过利用f(1)和f(0)的值，我们可以计算出f(2)的值。接着我们可以根据已知的值计算出f(3)、f(4)......
自下而上的动态规划实现：
int fDynamicDownUp(int n){
if (n == 0) return 0;
if (n == 1) return 1;
int[] num = new int[n];
num[0] = 0;
num[1] = 1;
for (int i = 2; i < n; i ) {
num[i] = num[i-1] num[i-2];
}
return num[n-1] num[n-2];
}
时间复杂度: O(n)
空间复杂度: O(n)
方法4：空间优化方法3观察方法3，你会发现num[i]只会被使用2次：
num[i 1] = num[i] num[i-1]
num[i 2] = num[i 1] num[i]
我们可以用变量来存储中间值，不需要使用额外的num数组来存储中间值。
空间优化方法实现：
int fDynamicSpaceOpt(int n){
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b= 1;
for (int i = 2; i < n; i ) {
int c = a b;
a = b;
b = c;
}
return a b;
}
时间复杂度: O(n)
空间复杂度: O(1)
