Day41——Dp专题 怼烎@ 2024-03-31 16:32 115阅读 0赞 #### 文章目录 #### * * 四、完全背包 * * * 01背包的核心代码 * 完全背包的核心代码 * 12、零钱兑换 II * 13、组合总和 Ⅳ * 14、 爬楼梯(进阶版) * 15.零钱兑换 * 16.完全平方数 * 17.单词拆分 -------------------- ### 四、完全背包 ### **完全背包:每一个物品可以选无限次** **完全背包和01背包问题唯一不同的地方就是,每种物品有无限件** ##### 01背包的核心代码 ##### 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]); } } 我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。 **而完全背包的物品是可以添加多次的,所以要从小到大去遍历,即:** ##### 完全背包的核心代码 ##### // 先遍历物品,再遍历背包 for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } * 在一维数组中,**01背包问题**必须先遍历物品,后遍历背包。**完全背包**两个for循环嵌套顺序是无所谓的 * 在一维数组中,**01背包问题**遍历背包时必须倒序遍历。**完全背包**正序遍历 * **倒序遍历**,必须先遍历物品,再遍历背包。**正序遍历**,则for循环嵌套顺序无所谓 **Code** //先遍历物品,再遍历背包 private static void testCompletePack(){ int[] weight = { 1, 3, 4}; int[] value = { 15, 20, 30}; int bagWeight = 4; int[] dp = new int[bagWeight + 1]; for (int i = 0; i < weight.length; i++){ // 遍历物品 for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } for (int maxValue : dp){ System.out.println(maxValue + " "); } } //先遍历背包,再遍历物品 private static void testCompletePackAnotherWay(){ int[] weight = { 1, 3, 4}; int[] value = { 15, 20, 30}; int bagWeight = 4; int[] dp = new int[bagWeight + 1]; for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量 for (int j = 0; j < weight.length; j++){ // 遍历物品 if (i - weight[j] >= 0){ dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]); } } } for (int maxValue : dp){ System.out.println(maxValue + " "); } } #### 12、零钱兑换 II #### [力扣题目链接][Link 1] * **组合不强调元素之间的顺序,排列强调元素之间的顺序** **思路**: **动规五部曲** * **确定dp数组以及下标的含义** dp\[j\]:凑成总金额j的货币组合数为dp\[j\] * **确定递推公式** dp\[j\] 就是所有的dp\[j - coins\[i\]\](考虑coins\[i\]的情况)相加。 所以递推公式:dp\[j\] += dp\[j - coins\[i\]\]; * **dp数组初始化** 首先dp\[0\]一定要为1,dp\[0\] = 1是 递归公式的基础,下标非0的dp\[j\]初始化为0,这样累计加dp\[j - coins\[i\]\]的时候才不会影响真正的dp\[j\] * **确定遍历顺序** **求组合数,先遍历物品,再遍历背包** for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量 dp[j] += dp[j - coins[i]]; } } **求排列数,先遍历背包,再遍历物品** for (int j = 0; j <= amount; j++) { // 遍历背包容量 for (int i = 0; i < coins.size(); i++) { // 遍历物品 if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]]; } } * **举例推导dp数组** ![image-20221208190623089][] * **如果求组合数就是外层for循环遍历物品,内层for遍历背包**。 * **如果求排列数就是外层for遍历背包,内层for循环遍历物品**。 **Code** class Solution { public int change(int amount, int[] coins) { //递推表达式 int[] dp = new int[amount + 1]; //初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装 dp[0] = 1; for (int i = 0; i < coins.length; i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } } #### 13、组合总和 Ⅳ #### [力扣题目链接][Link 2] 本题与零钱兑换差别就在于**物品和背包的遍历顺序** **动规五部曲** * **确定dp数组以及下标的含义** dp\[i\]: 凑成目标正整数为i的排列个数为dp\[i\] * **确定递推公式** dp\[i\] += dp\[i - nums\[j\]\]; * **dp数组如何初始化** dp\[0\] = 1 * **确定遍历顺序** 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 遍历顺序:**target(背包)放在外循环,将nums(物品)放在内循环,内循环从前到后遍历**。 * **举例推导dp数组** ![image-20221208192928500][] **Code** class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 0; i <= target; i++) { for (int j = 0; j < nums.length; j++) { if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } } #### 14、 爬楼梯(进阶版) #### [力扣题目链接][Link 3] **题目改为:一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢?** **思路**: **动规五部曲**: * **确定dp数组以及下标的含义** dp\[i\]:爬到有i个台阶的楼顶,有dp\[i\]种方法。 * **确定递推公式** 本题呢,dp\[i\]有几种来源,dp\[i - 1\],dp\[i - 2\],dp\[i - 3\] 等等,即:dp\[i - j\] 那么递推公式为:dp\[i\] += dp\[i - j\] * **dp数组初始化** 既然递归公式是 dp\[i\] += dp\[i - j\],那么dp\[0\] 一定为1,dp\[0\]是递归中一切数值的基础所在,如果dp\[0\]是0的话,其他数值都是0了。 下标非0的dp\[i\]初始化为0,因为dp\[i\]是靠dp\[i-j\]累计上来的,dp\[i\]本身为0这样才不会影响结果 * **确定遍历顺序** 这是背包里求排列问题,即:1、2 步 和 2、1 步都是上三个台阶,但是这两种方法不一样! 所以需将背包放在外循环,而物品放在内循环。 * **举例并推导dp数组** ![image-20221209090542359][] **总结** **本题看起来是一道简单题目,稍稍进阶一下其实就是一个完全背包!** 如果我来面试的话,我就会先给候选人出一个 本题原题,看其表现,如果顺利写出来,进而在要求每次可以爬\[1 - m\]个台阶应该怎么写。 顺便再考察一下两个for循环的嵌套顺序,为什么target放外面,nums放里面。 这就能考察对背包问题本质的掌握程度,候选人是不是刷题背公式,一眼就看出来了。 这么一连套下来,如果候选人都能答出来,相信任何一位面试官都是非常满意的。 **本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包,而且题目进阶的内容在leetcode上并没有原题,一定程度上就可以排除掉刷题党了,简直是面试题目的绝佳选择!** **Code** **爬楼梯** class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; int[] weight = { 1,2}; dp[0] = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j < weight.length; j++) { if (i >= weight[j]) dp[i] += dp[i - weight[j]]; } } return dp[n]; } } **爬楼梯(进阶版)** class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 0; i <= target; i++) { for (int j = 0; j < nums.length; j++) { if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } } #### 15.零钱兑换 #### [力扣题目链接][Link 4] **思路** **动规五部曲** * **确定dp数组以及下标的含义** dp\[j\]:凑足总额为j所需钱币的最少个数为dp\[j\] * **确定递推公式** 凑足总额为j - coins\[i\]的最少个数为dp\[j - coins\[i\]\],那么只需要加上一个钱币coins\[i\]即dp\[j - coins\[i\]\] + 1就是dp\[j\](考虑coins\[i\]) 所以dp\[j\] 要取所有 dp\[j - coins\[i\]\] + 1 中最小的。 递推公式:**dp\[j\] = min(dp\[j - coins\[i\]\] + 1, dp\[j\]);** * **dp数组如何初始化** **dp\[0\] = 0;** 其他下标对应的数值呢? 考虑到递推公式的特性,dp\[j\]必须初始化为一个最大的数,否则就会在min(dp\[j - coins\[i\]\] + 1, dp\[j\])比较的过程中被初始值覆盖。 **所以下标非0的元素都是应该是最大值。** * **确定遍历顺序** 所以本题并**不强调**集合是组合还是排列。 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。 遍历顺序不做要求,但我们采用**物品放外层,背包放内层。** * **举例推导dp数组** ![image-20221209091438692][] dp\[amount\]为最终结果。 **Code** class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; Arrays.fill(dp,max); dp[0] = 0; for(int i : coins){ for(int j = i; j <= amount; j++){ if(dp[j - i] != max){ dp[j] = Math.min(dp[j], dp[j - i] + 1); } } } return dp[amount] == max ? -1 : dp[amount]; } } #### 16.完全平方数 #### [力扣题目链接][Link 5] **思路** **动规五部曲** * **确定dp数组以及下标的含义** dp\[j\]:和为j的完全平方数的最少数量为dp\[j\] * **确定递推公式** dp\[j\] = min(dp\[j - i \* i\] + 1, dp\[j\]); * **dp数组初始化** dp\[0\]表示 和为0的完全平方数的最小数量,那么dp\[0\]一定是0 从递归公式dp\[j\] = min(dp\[j - i \* i\] + 1, dp\[j\]);中可以看出每次dp\[j\]都要选最小的,**所以非0下标的dp\[j\]一定要初始为最大值,这样dp\[j\]在递推的时候才不会被初始值覆盖**。 * **确定遍历顺序** 本题外层for遍历背包,内层for遍历物品,还是外层for遍历物品,内层for遍历背包,都是可以的! for (int i = 1; i * i <= n; i++) { // 遍历背包 for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1); } * **举例并推导dp数组** ![image-20221209101219544][] **Code** class Solution { public int numSquares(int n) { int max = Integer.MAX_VALUE; int[] dp = new int[n + 1]; Arrays.fill(dp,max); dp[0] = 0; // 遍历物品 for (int i = 1; i * i <= n; i++) { // 遍历背包 for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1); } } return dp[n]; } } #### 17.单词拆分 #### [力扣题目链接][Link 6] **思路** **动规五部曲** * **确定dp数组以及下标的含义** dp\[i\] : 字符串长度为i的话,dp\[i\]为true,表示可以拆分为一个或多个在字典中出现的单词。 * **确定递推公式** 如果确定dp\[j\] 是true,且 \[j, i\] 这个区间的子串出现在字典里,那么dp\[i\]一定是true。(j < i )。 所以递推公式是 if(\[j, i\] 这个区间的子串出现在字典里 && dp\[j\]是true) 那么 dp\[i\] = true。 * **dp数组如何初始化** dp\[0\]一定要为true,下标非0的dp\[i\]初始化为false * **确定遍历顺序** 本题求排列数,排列数就是外层for遍历背包,内层for循环遍历物品。 * **举例推导dp数组** ![image-20221209105723265][] dp\[s.size()\]就是最终结果。 **Code** class Solution { public boolean wordBreak(String s, List<String> wordDict) { boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; for (int i = 1; i <= s.length(); i++) { for (String word : wordDict) { int len = word.length(); if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) { dp[i] = true; break; } } } return dp[s.length()]; } } [Link 1]: https://leetcode.cn/problems/coin-change-ii/ [image-20221208190623089]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e09457e2b25f49ee9ff22e04ace25f35.png [Link 2]: https://leetcode.cn/problems/combination-sum-iv/ [image-20221208192928500]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6b6cbadf0c274500ba0c52fe674d1a24.png [Link 3]: https://leetcode.cn/problems/climbing-stairs/ [image-20221209090542359]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/40631b9f5e224cd0919fa48836c14e22.png [Link 4]: https://leetcode.cn/problems/coin-change/ [image-20221209091438692]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2c96591232924ce696a0e5eed6c12a8d.png [Link 5]: https://leetcode.cn/problems/perfect-squares/ [image-20221209101219544]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3f125d08a6234778a8cfddb9792fdde0.png [Link 6]: https://leetcode.cn/problems/word-break/ [image-20221209105723265]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/de240bbac6294482b82d9c841a714f1a.png
相关 Day38——Dp专题 DP专题 动态规划五部曲: 确定dp数组以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 1.斐波 怼烎@/ 2024年03月31日 12:42/ 0 赞/ 70 阅读
相关 dp专题题目记录 1.数的划分 2星 [https://ac.nowcoder.com/acm/problem/16695][https_ac.nowcoder.com_acm_prob 青旅半醒/ 2023年08月17日 16:26/ 0 赞/ 154 阅读
相关 动态规划dp专题 dp专题 斐波那契数列 01背包问题 最长不重复子字符串的长度 分割数组的最大值 最长公共子序列 最大子序和 买卖股票的最佳时期 爱被打了一巴掌/ 2023年07月17日 09:57/ 0 赞/ 26 阅读
相关 Day41——MyBatis逆向工程 一. 知识储备 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG 一时失言乱红尘/ 2023年07月04日 15:49/ 0 赞/ 5 阅读
还没有评论,来说两句吧...