斐波那契数列：
f(n)=f(n-1)+f(n-2)(n>2) f(0)=1;f(1)=1;
即有名的兔子繁衍问题
在本篇文章我将会给出三种解法

方法一： 递归

static int f1(int i) {
        if (i == 1 || i == 2)
            return 1;
        else
            return f1(i - 1) + f1(i - 2);
    }

1.时间复杂度 O(2^n)
首先可以根据函数递归执行顺序画出下图的二叉树结构（假设求第五个斐波那契数）

image.png

2.空间复杂度 O(1)

image.png

①-③：调用Fib(5),首先需调用Fib(4),Fib(4)要先调用Fib(3)，逐步调用直至返回Fib(2)的值1，Fib执行结束，所创建空间销毁。此时Fib(5)、Fib(4)、Fib(3)均未调用结束，程序共占用4个函数栈帧空间。

④-⑨：Fib(2)执行结束，接下来调用Fib(1)，创建一个函数栈帧空间，调用结束返回1后，该空间销毁，此时可得到Fib(3)=2，通过第⑦步返回Fib(3)的值，第⑧步同样创建空间再次调用Fib(2)，调用结束销毁空间，此时可得到Fib(4)=3，通过第⑨步返回Fib(4)的值，此过程最大占用4个函数栈帧空间。

⑩-···：最后和上面一样，调用Fib(3)，将返回值传给Fib(5)的模块，最终得到Fib(5)=5。

整个程序执行过程中，最多占用4个函数栈帧空间的大小，设一个函数栈帧空间为C
因此可得知当n=5时，该程序空间复杂度为O(4C)=>O(1)
当求第n个斐波那契数时，程序空间复杂度为O(n-1)C (n是常数)=>O(1)

方法二：循环

image.png

static int f2(int n) {
        int count = 1;
        int Fn_1 = 1;
        int Fn_2 = 1;
        while (n > 2) {
            Fn_2 = Fn_1;
            Fn_1 = count;
            count = Fn_1 + Fn_2;
            n--;
        }
        return count;
    }

1.时间复杂度 O(n)
程序中循环了n-2次，时间复杂度为O(n-2),保留最高阶时间复杂度为O(n)

2.空间复杂度 O(1)
该程序中创建了3个变量，即创建了3个内存空间，空间复杂度为O(3)即O(1)

方法三：尾递归

image.png

int fib(int n) {
    int pre = 1;
    int ppre = 0;
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        ret = pre + ppre;
        ppre = pre;
        pre = ret;
    }
    return ret;
}

1.时间复杂度 O(n)
根据尾递归的图解可看出，计算Fib(1,1,5)时，函数调用了3次，那么计算Fib(1,1,n)时，函数将调用n-2次，
由此可得时间复杂度为O(n-2)即O(n)。

2.空间复杂度 O(n)

image.png

尾递归的方法，需开辟n-2个空间，空间复杂度为O(n-2)即O(n)。

方法四：记忆化搜索(Memory Search)

记忆化搜索，即在搜索过程中记录下搜索结果，在下次的搜索过程中如果算出过这个结果，就可以直接拿来用。
时间复杂度O(N), 空间复杂度O(n)

/**
     * memory search
     * 递归
     * 时间复杂度O(N), 空间复杂度O(n)
     * @param n
     * @return
     */
    public static int fib_ms(int n){
        if(n==0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int[] memory = new int[n+1];
        if(memory[n] != 0){
            return memory[n];
        }
        memory[n] = fib_ms(n-1) + fib_ms(n-2);
        return memory[n];
    }

方法五：动态规划(Dynamic Programming)

非递归，减少了系统栈的建立，比记忆化搜索还快，将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案
时间复杂度O(N), 空间复杂度O(1)

/**
     * dynamic programming
     * 非递归，减少了系统栈的建立，比记忆化搜索还快
     * 将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案
     * 时间复杂度O(N), 空间复杂度O(1)
     * @param n
     * @return
     */
    public static int fib_dp(int n){
        if(n==0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int pre = 1;
        int ppre = 1;
        int result = 0;
        for(int i=3; i<=n; i++){
            result = pre + ppre;
            ppre = pre;
            pre = result;
        }
        return result;
    }

————————————————
原文链接：https://blog.csdn.net/lxf_style/java/article/details/80458519