代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录第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]

代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ,算法

综合代码：文章来源地址https://www.toymoban.com/news/detail-857079.html

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 <= 200

1 <= nums[i] <= 1000

nums 中的所有元素 互不相同

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数组：代码随想录第44天|动态规划：完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ,算法

和上一题的不同之处在于遍历顺序不同。

综合代码：

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. 组合总和 Ⅳ的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！