动态规划：完全背包理论基础
动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| 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
动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| 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. 组合总和 Ⅳ
动态规划之完全背包，装满背包有几种方法？求排列数？| 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的组合数量
}
}
