动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

二、动态规划的用途

求解多阶段决策问题：这里的「阶段」就是生活语言：解决一个问题分很多步骤，每一个步骤又有很多种选择，这一点和「回溯算法」是一样的，通常可以把多阶段决策问题画成一张树形图。

三、动态规划的基本思想

1.思想一：穷举法

动态规划没有为具体的问题设计特殊的解法，动态规划的方法在 每一阶段考虑了所有可能的情况，并且记录每一步的结果。但是我们通常不建议运用这个方法思想去解决大多数问题，但是他又是每个优化解法的基础，所以大家不要对穷举法产生排斥心理。

2.思想二：空间换时间

表格法（programming）的语义是非常准确的，可以用动态规划解决的问题，很多时候就是让我们在求解问题的过程中，记录每一步求解的结果。其实还是 空间换时间 思想的体现。

四、斐波那契数列

1.思维导图

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

示例一：

输入：2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例二：

输入：3

输出：2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2

思路分析：当给定计算的项数为 0 或者 1的时候，结果是他们本身。当所给定的项数是大于1的时候我们就可以用通项公式F(N) = F(N - 1) + F(N - 2)（其中 N > 1）

2.方法一：递归求解


public class recursion { 
 
    public int fib(int N) { 
        if (N < 2) { 
            return N; 
        } else { 
            return fib(N - 1) + fib(N - 2);
               }
         }
 }

复杂度分析：

时间复杂度： $O((\frac{1+\sqrt{5}}{2})^{N})$
空间复杂度：O(logN)，空间复杂度取决于递归调用栈的深度。

在代码执行过程中大量的重复计算

既然有重复问题，解决的办法是使用「缓存」，在遇到新问题的时，求解完成以后记录下来，之后再遇到同样规模的问题的时候，就查缓存数组里已经计算过的答案。

3.方法二：递归+缓存


public class recursion {
 
    public int fib(int N) {
        if (N < 2) {
            return N;
        }
 
        // 建立一个缓存数组，0 要占一个位置，所以设置 N + 1 个位置
        int[] memo = new int[N + 1];
        // 还未计算过的值用 -1 表示
        //memo是一个数组变量，-1是一个memo中元素数据类型的值，作用：填充memo数组中的每个元素        
        //都是-1
        Arrays.fill(memo, -1);
        return fib(N, memo);
    }
 
    public int fib(int n, int[] memo) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        //判断接下来的一项也就是从第二项开始，判断数组里面的数字是否为 -1 //如果是那就将前         
        //n - 1项和前 n - 2项 的数值相加，并修改此处 -1 的值
        if (memo[n] == -1) {
            memo[n] = fib(n - 1) + fib(n - 2);
        }
        return memo[n];
    }
}

复杂度分析：

时间复杂度：O(N)；
空间复杂度：O(N)，缓存大小为 N，递归调用栈的深度为logN。

4.方法三：动态规划

自底向上通过递推求解问题的过程与递归 + 缓存的方式的区别在于：每一次要计算的 F(N) 的值所依赖的 F(N - 1) 和 F(N - 2) 一定已经被计算出来了。


public class recursion{
 
    public int fib(int N) {
        if (N < 2) {
            return N;
        }
        //状态数组 自底向上 dp递推方式
        int[] dp = new int[N + 1];
        // 初始化
        dp[0] = 0;
        dp[1] = 1;
        // 递推开始
        for (int i = 2; i < N + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
}

复杂度分析：

时间复杂度：O(N)；
空间复杂度：O(N)；

这里「自底向上」通过递推的方式，一步一步推导得到最终结果的方式就是 动态规划。

总结

对于动态规划求解每一段的问题，是很重要的
动态规划一般来说只求最优解，不问具体过程。
在本次学习中运用了自顶向下，自底向上，可以多加练习掌握

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/909372