代码随想录

布满荆棘的人生 2024-02-22 09:45 53阅读 0赞

## 前言 ##

代码随想录算法训练营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

提示：

yaml

复制代码

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

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/co…][leetcode.cn_problems_co]

### 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 中的每个大于或等于该面额的元素的值。

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

css

复制代码

`初始化 dp[0]=1dp[0]=1； 遍历 coinscoins，对于其中的每个元素 coincoin，进行如下操作： 遍历 ii 从 coincoin 到 amountamount，将 dp[i−coin]dp[i−coin] 的值加到 dp[i]dp[i]。 最终得到 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

提示：

yaml

复制代码

`1 <= nums.length <= 200 1 <= nums[i] <= 1000 nums 中的所有元素 互不相同 1 <= target <= 1000`

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/co…][leetcode.cn_problems_co 1]

### 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\] 之和。

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

css

复制代码

`初始化 dp[0]=1dp[0]=1； 遍历 ii 从 11 到 targettarget，对于每个 ii，进行如下操作： 遍历数组 numsnums 中的每个元素 numnum，当 num≤inum≤i 时，将 dp[i−num]dp[i−num] 的值加到 dp[i]dp[i]。 最终得到 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]; } }`

[leetcode.cn_problems_co]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcoin-change-ii
[leetcode.cn_problems_co 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcombination-sum-iv