加强网站建设,网站点击代码,wordpress静态分离,网页建设企业目录 一、简介1.1 什么是动态规划#xff1f;1.2 动态规划的两种形式1#xff09;自顶向下的备忘录法#xff08;记忆化搜索法#xff09;2#xff09;自底向上的动态规划3#xff09;两种方法对比 1.3 动态规划的 3 大步骤 二、小试牛刀#xff1a;钢条切割2.1 题目描述… 目录 一、简介1.1 什么是动态规划1.2 动态规划的两种形式1自顶向下的备忘录法记忆化搜索法2自底向上的动态规划3两种方法对比 1.3 动态规划的 3 大步骤 二、小试牛刀钢条切割2.1 题目描述2.2 题目解析1第一步定义数组元素的含义2第二步找出数组元素之间的关系3第三步找出初始值 2.3 最优子结构2.4 代码实现1递归版本2备忘录版本3自底向上的动态规划 一、简介
1.1 什么是动态规划
在说明动态规划前我们先来了解一个小场景
A: 11111111A: 上面等式的值是多少
B: 计算... 8!A: 在上面等式的左边写上 1此时等式的值为多少
B: 立刻回答 9!
A: 你这次怎么这么快就知道答案了
B: 只要在8的基础上加1就行了由上面的小故事可知动态规划 就是 通过记住历史的求解结果来节省时间 。
1.2 动态规划的两种形式
示例斐波那契数列又称黄金分割数列其数值为1、1、2、3、5、8、13、21、34递推公式为 F ( 0 ) 1 , F ( 1 ) 1 , F ( n ) F ( n − 1 ) F ( n − 2 ) , n 2 , n ∈ N ∗ F(0)1,F(1)1, F(n)F(n-1)F(n-2),n2,n∈N^{*} F(0)1,F(1)1,F(n)F(n−1)F(n−2),n2,n∈N∗ 这个算法用递归来实现非常简单代码如下
public int fib(int n) {if (n 2) {return 1;}return fib(n - 1) fib(n - 2);
}先来分析一下递归算法的执行流程假如输入 6那么执行的递归树如下 我们可以发现
上面的递归树中每一个结点都会执行一次很多结点被重复执行。
为了避免这种情况我们可以把执行过的结点值保存下来后面用到直接查表这样可以节省大量时间。
下面看下保存历史记录的两种形式自顶向下的备忘录法、自底向上的动态规划。
1自顶向下的备忘录法记忆化搜索法
备忘录法也叫记忆化搜索法是比较好理解的
创建了一个 n1 大小的数组来保存求出斐波那契数列中的每一个值在递归的时候如果发现之前已经算过了就不再计算如果之前没有计算则计算后放入历史记录中。
public static void main(String[] args) {int n 6;// 声明数组用于记录历史初始化为-1int[] his new int[n 1];Arrays.fill(his, -1);System.out.println(fib(n, his));
}public static int fib(int n, int[] his) {if (n 2) {return 1;}// 读取历史if (his[n] ! -1) {return his[n];}int result fib(n - 1, his) fib(n - 2, his);// 记录历史his[n] result;return result;
}2自底向上的动态规划
备忘录法还是利用了递归不管怎样当计算 fib(6) 的时候还是要去先计算出 fib(1) ~ fib(5)那么为何不先计算出 f(1) ~ f(5) 呢这就是动态规划的核心先计算子问题再由子问题计算父问题。
public static int fib(int n) {int[] arr new int[n 1];arr[0] 1;arr[1] 1;for (int i 2; i n; i) {arr[i] arr[i - 2] arr[i - 1];}return arr[n];
}自底向上的动态规划方法也是利用数组保存了计算的值为后面的计算使用。
内存空间优化
我们观察上面的代码会发现参与循环的只有 fib(i)、fib(i-1)、fib(i-2) 项因此该方法的空间可以进一步的压缩如下
public static int fib(int n) {int num_i 0;int num_i_1 1;int num_i_2 1;for (int i 2; i n; i) {num_i num_i_2 num_i_1;num_i_2 num_i_1;num_i_1 num_i;}return num_i;
}3两种方法对比
一般来说由于备忘录的动态规划形式使用了递归递归的时候会产生额外的开销所以不推荐。相比之下使用自底向上的动态规划方法要好些也更容易理解。
1.3 动态规划的 3 大步骤
动态规划无非就是利用 历史记录来避免我们的重复计算。这些历史记录的存储一般使用 一维数组 或 二维数组 来保存。
第一步定义数组元素的含义
上面说了我们用一个数组来保存历史数据假设用一维数组 dp[] 来保存。这个时候有一个非常重要的点如何规定数组元素的含义 即 dp[i] 代表什么意思
第二步找出数组元素之间的关系
动态规划类似于我们高中学习的 数学归纳法。当我们要计算 d[i] 时可以利用 dp[i-1]、dp[i-2] … dp[1] 来推导证明。
第三步找出初始值
学过 数学归纳法 的都知道虽然知道了数组元素之间的关系式后可以通过 dp[i-1] 和 dp[i-2] 来计算 dp[i]但是我们首先至少要知道 dp[0] 和 dp[1] 才能推导后面的值。dp[0] 和 dp[1] 就是所谓的初始值。
二、小试牛刀钢条切割
2.1 题目描述 2.2 题目解析
1第一步定义数组元素的含义
由题目可知
p[] 是价格数组长度为 i 英寸的钢条价格为 p[i]r[] 是最大收益数组长度为 i 英寸的钢条可以获得的最大收益为 r[i]钢条的价格不确定可能切割的收益更高也可能不切割的收益更高。
通过解析可知数组元素含义 长度为 i 英寸的钢条可以获得的最大收益为 r[i]。 注意 这里的 收益是指价格的总和比如2 英寸的钢条切割后收益为112相比之下不切割的 5 收益更高。 2第二步找出数组元素之间的关系
假如我们要对长度为 4 英寸的钢条进行切割所有切割方案如下 由图可见我们将 r[4] 的计算转换成了 r[1]~ r[3] 的计算。 r 4 m a x ( r 1 r 3 , r 1 r 1 r 2 , r 2 r 2 , p 4 ) ; r_{4}max(r_{1}r_{3},r_{1}r_{1}r_{2},r_{2}r_{2},p_{4}); r4max(r1r3,r1r1r2,r2r2,p4); 以此类推可以继续转换 r[3] 由图可见我们继续将 r[3] 的计算转换成了 r[1]~r[2] 的计算。 r 3 m a x ( r 1 r 2 , r 1 r 1 r 1 , p 3 ) r_{3}max(r_{1}r_{2},r_{1}r_{1}r_{1},p_{3}) r3max(r1r2,r1r1r1,p3) 以此类推可以继续转换 r[2] 由于 1 英寸的钢条无法切割所以 r[1]p[1]。 r 2 m a x ( r 1 r 1 , p 2 ) r_{2}max(r_{1}r_{1},p_{2}) r2max(r1r1,p2) 由于 r[2] 中包含了 r[1] r[1]那么 r[3] 中的 m a x ( r 1 r 2 , r 1 r 1 r 1 ) m a x ( r 1 r 2 ) max(r_{1}r_{2},r_{1}r_{1}r_{1})max(r_{1}r_{2}) max(r1r2,r1r1r1)max(r1r2) 由于 r[3] 中包含了 r[1] r[2]那么 r[4] 中的 m a x ( r 1 r 3 , r 1 r 1 r 2 ) m a x ( r 1 r 3 ) max(r_{1}r_{3},r_{1}r_{1}r_{2})max(r_{1}r_{3}) max(r1r3,r1r1r2)max(r1r3) 所以整理 r[1]、r[2]、r[3]、r[4] 为 r 1 p 1 r_{1}p_{1} r1p1 r 2 m a x ( r 1 r 1 , p 2 ) r_{2}max(r_{1}r_{1},p_{2}) r2max(r1r1,p2) r 3 m a x ( r 1 r 2 , p 3 ) r_{3}max(r_{1}r_{2},p_{3}) r3max(r1r2,p3) r 4 m a x ( r 1 r 3 , r 2 r 2 , p 4 ) r_{4}max(r_{1}r_{3},r_{2}r_{2},p_{4}) r4max(r1r3,r2r2,p4)
根据公式进行递推 r[n] 为 r n m a x ( r 1 r n − 1 , r 2 r n − 2 , . . . , r n / 2 r n − n / 2 , p n ) r_{n}max(r_{1}r_{n-1},r_{2}r_{n-2},...,r_{n/2}r_{n-n/2},p_{n}) rnmax(r1rn−1,r2rn−2,...,rn/2rn−n/2,pn)
3第三步找出初始值
其实初始值我们在第二步已经找出来了
r[1]p[1]1r[2]max(r[1]r[1],p[2])5
2.3 最优子结构
通过该题我们注意到为了求规模为n的原问题我们 先求解形式完全一样但规模更小的子问题。当完成首次 切割后我们 将两段钢条看成两个独立的钢条切割问题实例。我们 通过组合两个相关子问题的最优解并在所有可能的两段切割方案中选取组合收益最大者构成原问题的最优解。
我们称 钢条切割问题 满足 最优子结构 性质问题的最优解由相关子问题的最优解组合而成而这些子问题可以独立求解。
2.4 代码实现
1递归版本
递归很好理解思路和回溯法是一样的遍历所有解空间。但这里和上面斐波那契数列的不同之处在于这里在每一层上都进行了一次最优解的选择qMath.max(q, p[i]cut(n-i)); 这段代码就是选择最优解。
final static int[] p {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};public static int cut(int n) {if (n 0) {return 0;}int max Integer.MIN_VALUE;for (int i 1; i n; i) {max Math.max(max, p[i - 1] cut(n - i));}return max;
}2备忘录版本
备忘录方法无非是在递归的时候记录下已经调用过的子函数的值。钢条切割问题的经典之处在于自底向上的动态规划问题的处理理解了这个也就理解了动态规划的精髓。
public static int cutByHis(int n) {int[] p {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};int[] r new int[n 1];for (int i 0; i n; i) {r[i] -1;}return cut(p, n, r);
}public static int cut(int[] p, int n, int[] r) {int q -1;if (r[n] 0)return r[n];if (n 0)q 0;else {for (int i 1; i n; i)q Math.max(q, cut(p, n - i, r) p[i - 1]);}r[n] q;return q;
}3自底向上的动态规划
自底向上的动态规划问题中最重要的是要理解在子循环遍历中的 i 变量相当于上面两个方法中的 n 变量i-j 主要用于获取历史计算过的问题值。
final static int[] p {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};public static int cutByDP(int n) {int[] r new int[n 1];for (int i 1; i n; i) {int q -1;for (int j 1; j i; j)q Math.max(q, p[j - 1] r[i - j]);r[i] q;}return r[n];
}整理完毕完结撒花~ 参考地址
1.算法-动态规划 Dynamic Programming–从菜鸟到老鸟https://blog.csdn.net/u013309870/article/details/75193592
2.告别动态规划连刷40道动规算法题我总结了动规的套路https://blog.csdn.net/hollis_chuang/article/details/103045322
