常见算法题总结（剑指10）

题目：求斐波那契数列的第n项。写一个函数，输入n，求斐波那契数列的第n项。斐波那契数列的定义如下：0，1，1，2，3，5，...

方法1：递归即可。

Java代码如下

 public static int getValue(int n){
        if (n<=0){
            return 0;
        }
        if (n==1 || n==2){
            return 1;
        }
       return getValue(n-1) + getValue(n-2);
    }

缺点：会出现重复调用，效率不高。如下图所示

 方法2：动态规划。从f(0)f(1)开始，后一步的结果由依赖于前面，把中间计算的结果利用起来，避免重复计算。时间复杂度为O(n)。空间复杂度为O(1)

Java代码如下

public static int forGetValue(int n){
        if (n==0){
            return 0;
        }
        if (n ==1 || n ==2){
            return 1;
        }
        int pre = 1;
        int prepre=1;
        int current=0;
        //从第三项开始
        for (int i=2;i