零钱兑换问题 I
1、题目:力扣原题
2、分析
(1)结合我们之前分析的(动态规划解决背包问题),这里硬币有无限个对应完全背包问题。但又存在一点区别:纯完全背包是能否凑成总的金额,本题是要求凑成总金额的组合个数。
(2)要注意是求解组合 还是排列 问题。例如 221 和121可以表示一种组合或者两种排列。组合之间不强调元素之间的顺序,而排列强调元素之间的顺序。
DP五部曲分析如下:
1)确定dp含义
dp[j]: 表示凑成总金额j可以得到的货币组合总数;
2)确定递推公式‘’
dp[j] (考虑coins[i]的组合总和) 就是所有的dp[j - coins[i]](不考虑coins[i])相加。
所以递推公式:dp[j] += dp[j - coins[i]];
(求装满背包有几种方法,一般公式都是:dp[j] += dp[j - nums[i]];)
3)初始化
dp[0]=1,表示凑成金额为0的货币组合数为1;
4)确定遍历顺序
这里就要根据上面讨论的来进行区别,题目是要求组合数还是排列数需要对遍历顺序进行处理。因为纯完全背包求得是能否凑成总和,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!
而本题要求凑成总和的组合数,元素之间要求没有顺序。所以纯完全背包是能凑成总和就行,不用管怎么凑的。本题是求凑出来的方案个数,且每个方案个数是为组合数。那么本题,两个for循环的先后顺序可就有说法了。
为了清晰对比,我们对两个for循环的先后遍历顺序讨论一下:
a、外层for循环遍历钱币, 内层for循环遍历金钱总额的情况
for (int i = 0; i < coins.size(); i++) { // 遍历物品(钱币数)
for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量(金钱总额),内层循环这里,背包容量必须大于物品大小才有意义,
//这个物品才可以装进背包,所以初始化j=coins[i]
dp[j] += dp[j - coins[i]];
}
}
因为金钱总额遍历在内循环,所以金钱总额里的每一个值只对应了钱币数的单次情况。例如,假设:coins[0] = 1,coins[1] = 2。
那么就是先把1加入计算,然后再把2加入计算,得到的方法数量只有{1, 2}这种情况。而不会出现{2, 1}的情况。所以这种先物品再背包的遍历顺序中dp[j]里计算的是组合数!
b、把两个for循环的遍历次序交换,先遍历金钱总额,再遍历钱币数
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]];
}
}
背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。先背包,在物品遍历,此时dp[j]里算出来的就是排列数!
为了进一步分析,我们采用dp五步曲中的第五步来展开讲解:
5)举例dp数组推导
输入: amount = 5, coins = [1, 2, 5] ,dp状态图如下:
我们采用先物品再背包的遍历顺序 来求解组合数:
最后 红色框中的结果就是最终的满足条件的组合数。
总结:
3、代码
java:
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];
}
}
python:
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount + 1)
dp[0] = 1
# 遍历物品
for i in range(len(coins)):
# 遍历背包
for j in range(coins[i], amount + 1):
dp[j] += dp[j - coins[i]]
return dp[amount]
----------------------------------------------------------------------------------------------------------------
零钱兑换问题 II
1、原题:力扣原题
(和问题1的区别:问题1是求解满足条件的所有组合数,本题是要求凑成金额的最少硬币个数;其中问题1和问题2的硬币数量都是无限的,即是完全背包问题 的深入)
2、分析
根据题目要求,最简单的一种思路便是把满足硬币组合等于amount的组合全部列出来,然后找到组合数目最少的即可,可以用递归解决,但时间复杂度会很高,需要很好的剪枝策略;
另一个直观的想法便是采用动态规划,初始化一个amount+1大小的dp数组,记录每一个状态的最优解,过程如下:
1)dp定义
dp[j]: 表示 可以凑成金额为j的最少硬币组合个数;
2) dp递归公式
得到dp[j](考虑coins[i]),只有一个来源,dp[j - coins[i]](没有考虑coins[i])。
凑足总额为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]);
3)初始化
首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;
其他下标对应的数值呢?
考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。
4)确定遍历顺序
故本题,任意顺序遍历都可,我们采用先遍历物品(硬币)再遍历背包(总金额);又因为硬币的个数有无数个,所以为完全背包问题,采用一维dp时,内层循环正序遍历即可。
3)代码文章来源:https://www.toymoban.com/news/detail-440840.html
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
//正序遍历:完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}
python:文章来源地址https://www.toymoban.com/news/detail-440840.html
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
'''版本一'''
# 初始化
dp = [amount + 1]*(amount + 1)
dp[0] = 0
# 遍历物品
for coin in coins:
# 遍历背包
for j in range(coin, amount + 1):
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] < amount + 1 else -1
到了这里,关于动态规划——零钱兑换问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!