题目描述

输入一个整数 n ，求斐波那契数列的第 n 项。假定从 0 开始，第 0 项为 0。(n≤39)

样例

输入整数 n=5 

返回 5

算法1

递归算法

最简单的直接书写方法，类似于电脑模拟人的想法一步步实现，最接近普通大众算法的解法

由于存在大量的重复计算时间复杂度为O($2^n$)

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0||n==1) return n;
        return Fibonacci(n-1)+Fibonacci(n-2);
        //下面是最简单的动态规划思想算法
       /* int dp[n+1];
        dp[0] =0; dp[1] = 1;
        for(int i=2;i<=n;i++) {
        dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];*/

    }
};

算法2

迭代算法，使用记录数值的方法一步一步的计算出结果，

时间复杂度：O（n）,秩序遍历一遍即可

参考文献

C++ 代码

class Solution {
public:
    int Fibonacci(int n) {
        int a=0,b=1;
        while(n--){
            int c=a+b;
            a=b;
            b=c;
        }
        return a;
        //if(n==0||n==1) return n;
        //return Fibonacci(n-1)+Fibonacci(n-2);
        //下面是最简单的动态规划思想算法
       /* int dp[n+1];
        dp[0] =0; dp[1] = 1;
        for(int i=2;i<=n;i++) {
        dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];*/

    }
};