以斐波那契来看从递归到动态规划的优化过程

对于递归的优化过程

• 暴力递归
• 对于暴力递归，某些计算过程是重复的，因此可以优化成记忆化递归。
• 而对于递归问题，一般都可以转换为动态规划。
• 而对于动态规划，我们又可以对dp数组进行优化，比如滚动数组的思想，可以将二维dp数组优化为一维dp数组，可以将一维dp数组优化为几个变量。

暴力递归

	public int fibonaci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return fibonaci(n - 1) + fibonaci(n - 2);
    }
复制代码

对于暴力递归，我们的**fibonaci(n – 1)和fibonaci(n – 2)**有很多重复计算，我们要想办法把已经计算过的结果都存储起来！

记忆化递归

	public int fibonaci2(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] memories = new int[n + 1];
        return process2(n, memories);
    }

    private int process2(int n, int[] memories) {
        int res = 0;
        // 如果memories中有记录，则直接return
        if (memories[n] != 0) {
            return memories[n];
        }
        if (n == 1 || n == 2) {
            res = 1;
        }
        if (n > 2){
            res = process2(n - 1, memories) + process2(n - 2, memories);
        }
        memories[n] = res;
        return res;
    }
复制代码

现在我们将已经已经计算过得结果放在memories中。如果memories中有记录，就不需要再去递归做重复计算。

动态规划

public int fibonaci3(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }
复制代码

动态规划的优化，滚动数组的思想

当然这题的dp数组是一维的，所以我们只需要几个变量来滚动向前就行了。

最小路径和这题的dp数组就是二维的，所以优化的话就是使用一维滚动数组。

public int fibonaci4(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int tmp;
        int pre = 1;
        int cur = 1;
        for (int i = 3; i <= n; i++) {
            tmp = cur;
            cur = pre + cur;
            pre = tmp;
        }
        return cur;
    }
复制代码

番外篇：快速幂

左神的书中的特别解法，这种解法是用了某些数学定理。定理说F(N)=F(N-1)+F(N-2)是严格的递推公式，所以一定有(F(n), F(n-1)) = (F(n-1), F(n-2)) * [[a, b], [c, d]]，状态矩阵： [[a, b], [c, d]]。带入f(1)，f(2)，f(3)，f(4)等，可以求出状态矩阵为{{1, 1}, {1, 0}}。