动态规划理论基础

 递归算法是一种穷举的展示，任何数学递推公式都可以直接转换成递归算法，递归算法是当前层需要上一层的准备。递归算法冗余计算的增长是爆炸性的。如果编译器的递归模拟算法要是能够保留一个预先算出的值的表，而对已经解过的子问题不用再进行递归调用，那么这种指数式的爆炸性的增长就可以避免

       动态规划就是这样的算法

       如果某一个问题可以解决很多重叠问题，那么使用动态规划是最有效的解决办法

       动态规划中的每一个状态是由上一个状态推导出来的，这和贪心算法是不同的，贪心算法是没有状态推导的过程，贪心算法都是在当前局部选取最优解。所以贪心算法解决不了动态规划的问题

       动态规划五部曲：

               1、确定dp数组（dp table）及下标的含义

               2、确定递推公式

               3、初始化dp数组

               4、确定遍历顺序

               5、举例推导dp数组

509. 斐波那契数

题目链接：力扣

思路

下面是对递归的优化：

用表优化递归

       从这道题目可以看出，递归算法是需要不断向下进行计算，进行压栈，比如要算F(5)，那就要先算出F(4)和F(3)，就要先算出F(3)、F(2)、F(2)、F(1)……，这里可以看到是有重复的运算的

       那我们可以先创建一个数组（表），能够保留一个预先算出的值，这样就可以不用，这样就避免了重复的运算。已经算过的F(n)就不用再进行重复的计算

       根据动态规划五部曲：

               1、确定dp数组（dp table）及下标的含义

                       第i个下标存储的是F(i)斐波那契的值

               2、确定递推公式

                       递推公式是：dp[i] = dp[i - 1]+dp[i - 2]

               3、初始化dp数组

                       dp[0] = 0;

                       dp[1] = 1;

               4、确定遍历顺序

                       从递推公式可以得出，后面的数字依赖前面的数字，所以是从前向后遍历

               5、举例推导dp数组

                       0 1 1 2 3 5 8 13 21 34 55

下面是对表的优化：

       得出动态对话的代码之后会发现，代码的内存消耗比较大，我们发现处理，中间过程中的数字不都用，但是还是占用了内存，这样的内存占用时浪费的。比如F(10)。dp数组为：0 1 1 2 3 5 8 13 21 34 55。但是只会返回55，前面的都不用

       其实只需要维护两个数值就可以了，不需要记录整个数列。在整个遍历的过程中

       dp[0] = dp[i - 1]

       dp[1] = dp[i - 2]

       最后循环结束的时候dp[1]就是我们要的值

斐波那契数

递归思路

class Solution {
    public int fib(int n) {
        // 终止条件
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

动态规划

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        // 创建数组
        int[] dp = new int[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];
    }
}

动态规划(优化数组)

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        // 创建数组
        int[] dp = new int[2];
        // 初始化数组
        dp[0] = 0;
        dp[1] = 1;
        // 遍历实现数组
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
}