💕"这种低水平质量的攻击根本就不值得我躲！"💕
作者：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),我们这里求的是最小值,只需要保证在填数据的时候不使用就行,那么就可以将无效数据设置为最大值,这样就不会使用到无效数据了
2.零钱兑换II
链接:
https://leetcode.cn/problems/coin-change-ii/
分析:
本题就是统计情况数
这道题就是完全背包版本的
目标和
代码:
class Solution {
public int change(int amount,int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];// 创建dp表
dp[0][0] = 1;// 初始化
// 填表
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] += dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
}
空间优化:
class Solution {
public int change(int amount,int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];// 创建dp表
dp[0] = 1;// 初始化
// 填表
for(int i = 1; i <= n; i++)
for(int j = coins[i - 1]; j <= amount; j++)
dp[j] += dp[j - coins[i - 1]];
return dp[amount];
}
}
三.完全平方数
链接:
https://leetcode.cn/problems/perfect-squares/
分析:
本题分析下来,要完成的操作就是使用尽可能少的完全平方数表示n,每个完全平方数的数目是无限制的(挑选的物品无限制就很有可能是完全背包问题)
注意这里最重要返回的结果是组合数最少的,其余的思路和完全背包问题一致,不做过多的讲解
class Solution {
public int numSquares(int n) {
int m = (int)Math.sqrt(n);// 求出数组的长度
int[][] dp = new int[m + 1][n + 1];// 创建dp表
for(int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;// 初始化
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j];
if(j - i * i >= 0)
dp[i][j] = Math.min(dp[i][j],dp[i][j - i * i] + 1);
}
}
return dp[m][n];
}
}
空间优化后的代码
class Solution {
public int numSquares(int n) {
int m = (int)Math.sqrt(n);// 求出数组的长度
int[] dp = new int[n + 1];// 创建dp表
for(int j = 1; j <= n; j++) dp[j] = 0x3f3f3f3f;// 初始化
for(int i = 1; i <= m; i++)
for(int j = i * i; j <= n; j++)
dp[j] = Math.min(dp[j],dp[j - i * i] + 1);
return dp[n];
}
}
