Day39——Dp专题 左手的ㄟ右手 2024-03-31 13:34 76阅读 0赞 #### 文章目录 #### * * * 01背包 * * 二维数组 * 一维数组 * 6.整数拆分 * 7.不同的二叉搜索 -------------------- #### 01背包 #### > 01背包：每一个物品只能选一次，选或者不选 状态标识：`f[i][j]`：所有只考虑前`i`个物品，且总体积不超`j`的所有选法的集合 属性：`Max` 状态计算：`f[i][j]` * w\[i\]代表重量，v\[i\]代表价值 * 不选第`i`个物品：`f[i][j] = f[i - 1][j]` * 选第`i`个物品：`f[i][j] = f[i - 1][j - w[i]] + v[i]` **二维数组** for(int i = 1; i <= n; i ++){ for(int j = 0; j <= m; j ++){ f[i][j] = f[i - 1][j]; if(j >= w[i]){ f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]); } } } **一维数组** for(int i = 1; i <= n; i ++){ for(int j = m; j >= w[i]; j --){ f[j] = Math.max(f[j], f[j - w[i]] + v[i]); } } ##### 二维数组 ##### 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。 ![image-20221130104023516][] **动规五部曲** * **确定dp数组以及下标的含义** dp\[i\]\[j\] 表示从下标为\[0-i\]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 ![image-20221130104257311][] * **确定递推公式** **不放物品i**： dp[i][j]=dp[i - 1][j] **放物品i**： dp[i][j]=dp[i - 1][j - weight[i]] + value[i] **递归公式** dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) * **dp数组如何初始化** 状态转移方程 `dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])`; 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。 `dp[0][j]`，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 那么很明显当 j < weight\[0\]的时候，`dp[0][j]` 应该是 0，因为背包容量比编号0的物品重量还小。 当j >= weight\[0\]时，`dp[0][j]` 应该是value\[0\]，因为背包容量放足够放编号0物品。 for (int j = 0 ; j < weight[0]; j++) { // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。 dp[0][j] = 0; } // 正序遍历 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } `dp[0][j] 和 dp[i][0]` 都已经初始化了，那么其他下标应该初始化多少呢 将其余都置为0 ![image-20221130104931698][] * **确定遍历顺序** 先遍历物品或者后遍历物品偶都可以运行通过 **先给出先遍历物品，然后遍历背包重量的代码** for(int i = 1; i <= n; i ++){ for(int j = 0; j <= m; j ++){ f[i][j] = f[i - 1][j]; if(j >= w[i]){ f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]); } } } **先给出先遍历背包重量，然后遍历物品的代码** for(int j = 0; j <= m; j ++){ for(int i = 1; i <= n; i ++){ f[i][j] = f[i - 1][j]; if(j >= w[i]){ f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i]] + v[i]); } } } **只要左上角和正上方有值就可以，所以先遍历背包或者先遍历物品都可以** ![image-20221130105439573][] * **举例推导dp数组** ![image-20221130105620787][] **Code** public static void main(String[] args) { int[] weight = { 1, 3, 4}; int[] value = { 15, 20, 30}; int bagsize = 4; dfs(weight, value, bagsize); } public static void dfs(int[] weight, int[] value, int bagsize){ int wlen = weight.length, value0 = 0; //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值 int[][] dp = new int[wlen + 1][bagsize + 1]; //初始化：背包容量为0时，能获得的价值都为0 for (int i = 0; i <= wlen; i++){ dp[i][0] = value0; } //遍历顺序：先遍历物品，再遍历背包容量 for (int i = 1; i <= wlen; i++){ for (int j = 1; j <= bagsize; j++){ if (j < weight[i - 1]){ dp[i][j] = dp[i - 1][j]; }else{ dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]); } } } //打印dp数组 for (int i = 0; i <= wlen; i++){ for (int j = 0; j <= bagsize; j++){ System.out.print(dp[i][j] + " "); } System.out.print("\n"); } } ##### 一维数组 ##### **动规五部曲分析如下：** * **确定dp数组的定义以及下标的含义** 在一维dp数组中，dp\[j\]表示：容量为j的背包，所背的物品价值可以最大为dp\[j\]。 * **dp数组的递推公式** dp\[j\]有两个选择，一个是取自己dp\[j\] 相当于 二维dp数组中的`dp[i-1][j]`，即不放物品i，一个是取dp\[j - weight\[i\]\] + value\[i\]，即放物品i，指定是取最大的，毕竟是求最大价值 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); * **dp数组的初始化** dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。 那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了 * **dp数组的遍历顺序** for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } **这里大家发现和二维dp的写法中，遍历背包的顺序是不一样的！** 二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。 为什么呢？ **倒序遍历是为了保证物品i只被放入一次！**。但如果一旦正序遍历了，那么物品0就会被重复加入多次！ 举一个例子：物品0的重量weight\[0\] = 1，价值value\[0\] = 15 如果正序遍历 dp\[1\] = dp\[1 - weight\[0\]\] + value\[0\] = 15 dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 30 **倒序就是先算dp\[2\]** dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 15 （dp数组已经都初始化为0） dp\[1\] = dp\[1 - weight\[0\]\] + value\[0\] = 15 所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。 **一维数组必须先遍历背包，之后在遍历背包容量** 因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp\[j\]就只会放入一个物品，即：背包里只放入了一个物品。 倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。 * **举例推导dp数组** ![image-20221130114813279][] **Code** public static void main(String[] args) { int[] weight = { 1, 3, 4}; int[] value = { 15, 20, 30}; int bagWight = 4; dfs(weight, value, bagWight); } public static void dfs(int[] weight, int[] value, int bagWeight){ int wLen = weight.length; //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值 int[] dp = new int[bagWeight + 1]; //遍历顺序：先遍历物品，再遍历背包容量 for (int i = 0; i < wLen; i++){ for (int j = bagWeight; j >= weight[i]; j--){ dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } //打印dp数组 for (int j = 0; j <= bagWeight; j++){ System.out.print(dp[j] + " "); } } **面试题目** 就是本文中的题目，要求先实现一个纯二维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写行不行？再讲一讲初始化的逻辑。 然后要求实现一个一维数组的01背包，最后再问，一维数组的01背包，两个for循环的顺序反过来写行不行？为什么？ 注意以上问题都是在候选人把代码写出来的情况下才问的。 **二维数组** * for循环遍历顺序不受限制，可以先遍历背包，也可以先遍历背包容量 * 正序遍历，倒叙遍历都可以 * 初始化 for (int j = 0 ; j < weight[0]; j++) { // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。 dp[0][j] = 0; } // 正序遍历 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } **一维数组** * 必须先遍历背包，之后遍历背包容量 * 必须倒叙遍历 * 初始化——都初始化为0 #### 6.整数拆分 #### [力扣题目链接][Link 1] 思路： **动规五部曲**： * **确定dp数组以及下标的含义** dp\[i\]：分拆数字i，可以得到的最大乘积为dp\[i\]。 * **确定递推公式** 一个是j \* (i - j) 直接相乘。 一个是j \* dp\[i - j\]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。 * **dp数组如何初始化** 初始化dp\[2\] = 1 * **确定遍历顺序** dp\[i\] 是依靠 dp\[i - j\]的状态，所以遍历i一定是从前向后遍历，先有dp\[i - j\]再有dp\[i\]。 for (int i = 3; i <= n ; i++) { for (int j = 1; j <= i / 2; j++) { dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); } } * **举例推导dp数组** ![image-20221129135402745][] **Code** class Solution { public int integerBreak(int n) { //dp[i] 为正整数 i 拆分后的结果的最大乘积 int[]dp=new int[n+1]; dp[2]=1; for(int i=3;i<=n;i++){ for(int j=1;j<=i-j;j++){ // 这里的 j 其实最大值为 i-j,再大只不过是重复而已， //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的， //j 最大到 i-j,就不会用到 dp[0]与dp[1] dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j])); // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘 //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。 } } return dp[n]; } } #### 7.不同的二叉搜索 #### [力扣题目链接][Link 2] **思路**： 当n为3的时候，有5颗二叉搜索树 ![image-20221129184437347][] dp\[3\]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 \* 左子树有0个元素的搜索树数量 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 \* 左子树有1个元素的搜索树数量 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 \* 左子树有2个元素的搜索树数量 有2个元素的搜索树数量就是dp\[2\]。 有1个元素的搜索树数量就是dp\[1\]。 有0个元素的搜索树数量就是dp\[0\]。 所以dp\[3\] = dp\[2\] \* dp\[0\] + dp\[1\] \* dp\[1\] + dp\[0\] \* dp\[2\] **如图所示**： ![image-20221129184535620][] **动规五部曲**： * **确定dp数组以及下标的含义** dp\[i\] ： 1到i为节点组成的二叉搜索树的个数为dp\[i\]。 * **确定递推公式** 递推公式：dp\[i\] += dp\[j - 1\] \* dp\[i - j\]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量 * **dp数组如何初始化** 初始化dp\[0\] = 1 dp\[1\]=1 dp[0] = 1; dp[1] = 1; * **确定遍历顺序** 从递归公式：dp\[i\] += dp\[j - 1\] \* dp\[i - j\]可以看出，节点数为i的状态是依靠 i之前节点数的状态。 那么遍历i里面每一个数作为头结点的状态，用j来遍历 for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } * **举例推导dp数组** ![image-20221129184835696][] Code class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ dp[i]+=dp[j-1]*dp[i-j]; } } return dp[n]; } } [image-20221130104023516]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e16d8ac8032c4f6e809b5e97f6d523b8.png [image-20221130104257311]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3c13ff62631a4e52aef64149ba56ca40.png [image-20221130104931698]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/34f3ed7327564e72855d154dc13dd336.png [image-20221130105439573]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/754c8a8d2d3544308af72335bcbd35df.png [image-20221130105620787]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/166f7af32b7a4a05b786a659357e61b3.png [image-20221130114813279]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d278a2d647064c7d913ad3f2292172d6.png [Link 1]: https://leetcode.cn/problems/integer-break/ [image-20221129135402745]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8723a779d6d942718b54065074253f56.png [Link 2]: https://leetcode.cn/problems/unique-binary-search-trees/ [image-20221129184437347]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/933dc2fe8b9640a59187fcb468f7314b.png [image-20221129184535620]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/150c9376b9e14e2bb88e7b06082dc5bd.png [image-20221129184835696]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5c8b06c1b5444d4c883d12151c362198.png
相关 Day38——Dp专题 DP专题 动态规划五部曲： 确定dp数组以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 1.斐波 怼烎@/ 2024年03月31日 12:42/ 0 赞/ 69 阅读
相关 dp专题题目记录 1.数的划分 2星 [https://ac.nowcoder.com/acm/problem/16695][https_ac.nowcoder.com_acm_prob 青旅半醒/ 2023年08月17日 16:26/ 0 赞/ 153 阅读
相关 动态规划dp专题 dp专题 斐波那契数列 01背包问题 最长不重复子字符串的长度 分割数组的最大值 最长公共子序列 最大子序和 买卖股票的最佳时期 爱被打了一巴掌/ 2023年07月17日 09:57/ 0 赞/ 20 阅读
相关 01背包专题（DP问题） 01背包的模板 小提醒：写01背包时要养成 初始化数组 和 从1开始循环 的习惯 \无优化 for(int i=1;i<=n;i++) { 妖狐艹你老母/ 2023年07月11日 08:40/ 0 赞/ 23 阅读
朴灿烈づ我的快乐病毒、
怼烎@
左手的ㄟ右手
柔情只为你懂
红太狼
爱被打了一巴掌
还没有评论，来说两句吧...