💕"这种低水平质量的攻击根本就不值得我躲！"💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(4)–完全背包拓展题目
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(4)--完全背包拓展题目
一.零钱兑换
链接:
https://leetcode.cn/problems/coin-change/submissions/517819340/
分析:
本题就是一个完全背包问题的体现,完全背包问题最大的特点就是物品的数量是无限制的,在本题中硬币的数量也是无限制的,所以本题依旧可以采用动态规划的思想解决
状态表示:
dp[i][j]:在[1,i]区间内的硬币中选择,实现总额为j元的最小硬币组合数
状态转移方程:
初始化:
由于可能无法使用一定组合的硬币实现j元,此时的状态应该为-1,在选择nums[i]这种情况下,为了不使用无效的数据所以我们需要特殊判断一下,目的是不使用无效的数据,那么只要在填表的时候无效数据不会被使用到即可,这里我们求的是两种情况的最小值,如果不想使用无效数据,可以将无效数据设置为0x3f3f3f3f,这样无效数据对我们的初始化就没有影响了
代码:
class Solution { public int coinChange(int[] coins, int amount) { int n = coins.length; int[][] dp = new int[n + 1][amount + 1];// 创建dp表 for(int j = 1; j <= amount; j++) dp[0][j] = 0x3f3f3f3f;// 初始化为最大值 for(int i = 1; i <= n; i++) { for(int j = 0; j <= amount; j++) { dp[i][j] = dp[i - 1][j]; if(j - coins[i - 1] >= 0)// 不能超过最大容量 dp[i][j] = Math.min(dp[i][j],dp[i][j - coins[i - 1]] + 1); } } // 注意这种恰好等于的背包问题 最后的返回值一定要特判一下 return dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount]; } }
空间优化:
class Solution { public int coinChange(int[] coins, int amount) { int n = coins.length; int[] dp = new int[amount + 1];// 创建dp表 for(int j = 1; j <= amount; j++) dp[j] = 0x3f3f3f3f;// 初始化为最大值 for(int i = 1; i <= n; i++) for(int j = coins[i - 1]; j <= amount; j++) dp[j] = Math.min(dp[j],dp[j - coins[i - 1]] + 1); // 注意这种恰好等于的背包问题 最后的返回值一定要特判一下 return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount]; } }
思考的难点:
- 如何通过设置无效的数据来进行初始化,在选nums[i]这种情况时,我们之所以要判断一下是为了不使用符合该条件的数据(无效数据 -1),我们这里求的是最小值,只需要保证在填数据的时候不使用就行,那么就可以将无效数据设置为最大值,这样就不会使用到无效数据了
算法系列--动态规划--背包问题(4)--完全背包拓展题目（下）https://developer.aliyun.com/article/1480861?spm=a2c6h.13148508.setting.16.352e4f0ecxYhMg
