本文主要是介绍代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划：完全背包理论基础
代码随想录 (programmercarl.com)
动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
完全背包中的物品可以添加多次，所以要从小到大遍历：
// 先遍历物品，再遍历背包
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]);// dp[j]表示背包容量为j时的最大价值// dp[j - weight[i]]表示背包容量为j减去当前物品重量时的最大价值// value[i]表示当前物品的价值// Math.max(dp[j], dp[j - weight[i]] + value[i])表示在不超过背包容量的情况下，选择装入当前物品或者不装入当前物品的最大价值}
}
518.零钱兑换II
518. 零钱兑换 II - 力扣（LeetCode）
代码随想录 (programmercarl.com)
动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意，你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
动规五部曲：
1、确定dp数组以及下标的含义：
dp[j] 凑成总金额j的货币组合数为dp[j];
2、确定递推公式：dp[j]就是所有的dp[j-coins[i]]相加，所以dp[j] += dp[j - coins[i]]
3、dp数组如何初始化：dp[0]=1;
4、确定遍历顺序：求组合是外层for循环遍历物品，内层for循环遍历背包；求排列就是外层for循环遍历背包，内层for循环遍历物品。
5、举例推导dp数组：输入：amounts=5, coins=[1,2,5]
综合代码：
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];}
}377. 组合总和 Ⅳ
377. 组合总和 Ⅳ - 力扣（LeetCode）
代码随想录 (programmercarl.com)
动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili
给你一个由 不同 整数组成的数组
nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。示例 2：
输入：nums = [9], target = 3 输出：0提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums中的所有元素 互不相同1 <= target <= 1000进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
动规五部曲：
1、确定dp数组以及下标的含义：dp[i]:凑成目标正整数为i的排列个数为dp[i];
2、确定递推公式：dp[i] += dp[i - nums[j]]；
3、dp数组如何初始化：dp[0]=1;
4、确定遍历顺序：如果求组合数就是外层for循环遍历物品，内层for循环遍历背包；
求排列数就是外层for循环遍历背包，内层for循环遍历物品；所以本题最终遍历顺序：target（背包）放在外层循环，nums(物品）放在内层循环，从前向后遍历；
5、举例推导dp数组：
和上一题的不同之处在于遍历顺序不同。
综合代码：
class Solution {// 定义一个名为Solution的类public int change(int amount, int[] coins) {// 创建一个名为change的公共方法，接受一个整数amount和一个整数数组coins作为参数，并返回一个整数int[] dp = new int[amount + 1];// 创建一个名为dp的整数数组，其长度为amount加1，用于存储不同金额的组合数量dp[0] = 1;// 初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装for (int i = 0; i < coins.length; i++) {// 遍历硬币数组for (int j = coins[i]; j <= amount; j++) {// 遍历金额，从当前硬币面额开始，直到目标金额dp[j] += dp[j - coins[i]];// 更新dp数组中的值，当前金额j的组合数量等于上一个金额(j - coins[i])的组合数量加上当前硬币的组合数量}}return dp[amount];// 返回目标金额amount的组合数量}
}
这篇关于代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
