题目：

现在要求输入一个整数n，请你输出斐波那契数列的第n项。

斐波那契数列的定义：

f(0)=0;f(1)=1;

f(n)=f(n-1)+f(n-2)

思路：

1、递归：

根据递推公式来实现

优点：代码简单，易懂

缺点：

• 效率低：函数递归调用过程中需要不断分配栈空间，且不断地入栈出栈，代码执行效率低；
• 栈溢出：当递归层级太多时，会超出栈容量，导致栈溢出；
• 复杂度高：递归调用存在大量的重复计算，时间复杂度以n的指数递增。

2、循环：

从下往上计算（动态规划），克服递归出现的缺陷

3、类似问题：

• 青蛙跳台阶：

(1)一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级台阶总共有多少种跳法？

f(n)=f(n-1)+f(n-2)

f(1)=1;

f(2)=2;

(2)一只青蛙一次可以跳上1级，2级。。。n级，此时一只青蛙跳上一个n级的台阶总共有多少种跳法?

f(n)=f(n-1)+f(n-2)*2

f(1)=1;

f(2)=2;

数学归纳法证明：f(n)=2^(n-1)

• 矩阵覆盖：

我们可以用2*1的小矩阵横着或者竖着去覆盖大的矩形，请问用8个2*1的小矩阵无重叠地覆盖一个2*8的大矩形，总共有多少种方法？

f(n)=f(n-1)+f(n-2)

f(1)=1;

f(2)=2;

代码：

#include 
     
      using namespace std;long long fibonacci_recursively(unsigned int n){    if(n<=0)        return 0;    if(n==1)        return 1;    return fibonacci_recursively(n-1)+fibonacci_recursively(n-2);}long long fibonacci_iteratively(unsigned int n){    if(n<2)        return n;    long long fibNMinusOne=1;    long long fibNMinusTwo=0;    long long fibN=0;    for(unsigned int i=2;i<=n;++i){        fibN=fibNMinusOne+fibNMinusTwo;        fibNMinusTwo=fibNMinusOne;        fibNMinusOne=fibN;    }    return fibN;}int main(){    cout <
      
       << endl;    cout <
       
        << endl;    return 0;}
       
      
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/c6c7742f5ba7442aada113136ddea0c3?rp=1

AC代码：

class Solution {public:	int Fibonacci(int n) {		if(n<2)            return n;        int fone=0;        int ftwo=1;        int fsum;        for(int i=2;i<=n;i++){            fsum=fone+ftwo;        	fone=ftwo;            ftwo=fsum;        }        return fsum;	}};