前言

代码随想录算法训练营day44

一、Leetcode 518. 零钱兑换 II

1.题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 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

提示：

1. 1 <= coins.length <= 300
2. 1 <= coins[i] <= 5000
3. coins 中的所有值 互不相同
4. 0 <= amount <= 5000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/coin-change-ii

2.解题思路

方法一：动态规划

这道题中，给定总金额 amountamount 和数组 coinscoins，要求计算金额之和等于 amountamount 的硬币组合数。其中，coinscoins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。

可以通过动态规划的方法计算可能的组合数。用 dp[x]dp[x] 表示金额之和等于 xx 的硬币组合数，目标是求 dp[amount]dp[amount]。

动态规划的边界是 dp[0]=1dp[0]=1。只有当不选取任何硬币时，金额之和才为 00，因此只有 11 种硬币组合。

对于面额为 coincoin 的硬币，当 coin≤i≤amountcoin≤i≤amount 时，如果存在一种硬币组合的金额之和等于 i−coini−coin，则在该硬币组合中增加一个面额为 coincoin 的硬币，即可得到一种金额之和等于 ii 的硬币组合。因此需要遍历 coinscoins，对于其中的每一种面额的硬币，更新数组 dpdp 中的每个大于或等于该面额的元素的值。

由此可以得到动态规划的做法：

1. 初始化 dp[0]=1dp[0]=1；
2. 
3. 遍历 coinscoins，对于其中的每个元素 coincoin，进行如下操作：
4.     遍历 ii 从 coincoin 到 amountamount，将 dp[i−coin]dp[i−coin] 的值加到 dp[i]dp[i]。
5. 
6. 最终得到 dp[amount]dp[amount] 的值即为答案。

上述做法不会重复计算不同的排列。因为外层循环是遍历数组 coinscoins 的值，内层循环是遍历不同的金额之和，在计算 dp[i]dp[i] 的值时，可以确保金额之和等于 ii 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。

例如，coins=[1,2]coins=[1,2]，对于 dp[3]dp[3] 的计算，一定是先遍历硬币面额 11 后遍历硬币面额 22，只会出现以下 22 种组合：

3=1+1+13=1+233=1+1+1=1+2

硬币面额 22 不可能出现在硬币面额 11 之前，即不会重复计算 3=2+13=2+1 的情况。

3.代码实现

```java class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } }
```

二、Leetcode 377. 组合总和 Ⅳ

1.题目

给你一个由 不同 整数组成的数组 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. 1 <= nums.length <= 200
2. 1 <= nums[i] <= 1000
3. nums 中的所有元素 互不相同
4. 1 <= target <= 1000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/combination-sum-iv

2.解题思路

方法一：动态规划

这道题中，给定数组 numsnums 和目标值 targettarget，要求计算从 numsnums 中选取若干个元素，使得它们的和等于 targettarget 的方案数。其中，numsnums 的每个元素可以选取多次，且需要考虑选取元素的顺序。由于需要考虑选取元素的顺序，因此这道题需要计算的是选取元素的排列数。

可以通过动态规划的方法计算可能的方案数。用 dp[x]dp[x] 表示选取的元素之和等于 xx 的方案数，目标是求 dp[target]dp[target]。

动态规划的边界是 dp[0]=1dp[0]=1。只有当不选取任何元素时，元素之和才为 00，因此只有 11 种方案。

当 1≤i≤target1≤i≤target 时，如果存在一种排列，其中的元素之和等于 ii，则该排列的最后一个元素一定是数组 numsnums 中的一个元素。假设该排列的最后一个元素是 numnum，则一定有 num≤inum≤i，对于元素之和等于 i−numi−num 的每一种排列，在最后添加 numnum 之后即可得到一个元素之和等于 ii 的排列，因此在计算 dp[i]dp[i] 时，应该计算所有的 dp[i−num]dp[i−num] 之和。

由此可以得到动态规划的做法：

1. 初始化 dp[0]=1dp[0]=1；
2. 
3. 遍历 ii 从 11 到 targettarget，对于每个 ii，进行如下操作：
4.     遍历数组 numsnums 中的每个元素 numnum，当 num≤inum≤i 时，将 dp[i−num]dp[i−num] 的值加到 dp[i]dp[i]。
5. 
6. 最终得到 dp[target]dp[target] 的值即为答案。

上述做法是否考虑到选取元素的顺序？答案是肯定的。因为外层循环是遍历从 11 到 targettarget 的值，内层循环是遍历数组 numsnums 的值，在计算 dp[i]dp[i] 的值时，numsnums 中的每个小于等于 ii 的元素都可能作为元素之和等于 ii 的排列的最后一个元素。例如，11 和 33 都在数组 numsnums 中，计算 dp[4]dp[4] 的时候，排列的最后一个元素可以是 11 也可以是 33，因此 dp[1]dp[1] 和 dp[3]dp[3] 都会被考虑到，即不同的顺序都会被考虑到。

3.代码实现

```java class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int num : nums) { if (num <= i) { dp[i] += dp[i - num]; } } } return dp[target]; } }
```