郑州建站优化,微信公众号推文模板素材,网站开发过程会遇到的问题,深圳市住房和建设局电话322. 零钱兑换 文章目录 [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)一、题目二、题解方法一#xff1a;完全背包二维数组方法二#xff1a;一维数组 三、注意 一、题目
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 a…322. 零钱兑换 文章目录 [322. 零钱兑换](https://leetcode.cn/problems/coin-change/)一、题目二、题解方法一完全背包二维数组方法二一维数组 三、注意 一、题目
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1示例 2
输入coins [2], amount 3
输出-1示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 231 - 10 amount 104
二、题解
方法一完全背包二维数组
这个问题可以看作是一个完全背包问题的变形即每种硬币的数量是无限的而不是有限的。 算法思路 首先我们要定义一个二维数组 dp 其中 dp[i][j] 表示用前 i1 种硬币即 coins[0] 到 coins[i]凑成金额 j 所需的最少硬币个数。 然后我们要初始化 dp 数组对于第一种硬币 coins[0] 我们只需要看金额 j 是否能被它整除如果能那么 dp[0][j] j / coins[0] 否则 dp[0][j] INT_MAX 表示无法凑成。 接下来我们要逐行更新 dp 数组对于第 i1 种硬币 coins[i] 我们有两种选择使用它或者不使用它。如果不使用它那么 dp[i][j] dp[i-1][j] 即和前 i 种硬币的结果一样如果使用它那么我们要保证金额 j 大于等于硬币面额 coins[i] 并且减去这个面额后的金额能够被前 i1 种硬币凑成即 dp[i][j-coins[i]] ! INT_MAX 那么 dp[i][j] dp[i][j-coins[i]] 1 即在减去这个面额后的结果上加一。我们要在这两种选择中取最小值即 dp[i][j] min(dp[i-1][j], dp[i][j-coins[i]] 1) 。 最后我们要返回 dp[coins.size() - 1][amount] 即用所有种类的硬币凑成总金额所需的最少硬币个数。如果这个值等于 INT_MAX 说明无法凑成返回 -1 否则返回这个值。 具体实现 可以用一个嵌套的循环来实现上述算法思路外层循环遍历硬币种类内层循环遍历金额。每次更新 dp[i][j] 时先赋值为不使用当前硬币的结果然后判断是否可以使用当前硬币并更新为最小值。 我们还需要注意一些边界情况比如当金额为零时返回零当硬币数组为空时返回 -1 。 class Solution {
public:int coinChange(vectorint coins, int amount) {if (amount 0) return 0;vectorvectorint dp(coins.size(), vectorint(amount 1, INT_MAX));// 初始化for (int i 0; i amount; i) {if (i % coins[0] 0) {dp[0][i] i / coins[0];}}for (int i 1; i coins.size(); i) {for (int j 0; j amount; j) {dp[i][j] dp[i - 1][j];if (j coins[i] dp[i][j - coins[i]]!INT_MAX) {dp[i][j] min(dp[i][j], dp[i][j - coins[i]] 1);}}}return dp[coins.size() - 1][amount] INT_MAX? -1 : dp[coins.size() - 1][amount];}
};算法分析 时间复杂度O(N*M)其中 N 是硬币种类数M 是总金额。我们需要遍历所有的硬币和金额组合每次更新一个状态值。 空间复杂度O(N*M)其中 N 是硬币种类数M 是总金额。需要一个二维数组来存储所有的状态值。
方法二一维数组
算法思路和具体实现和上面的二维数组差不多不过我也copy了一下~ 算法思路 首先我们定义一个一维数组 dp 其中 dp[j] 表示凑成金额 j 所需的最少硬币个数。然后我们初始化 dp 数组对于金额为零的情况我们不需要任何硬币所以 dp[0] 0 。对于其他金额我们先设为一个很大的数比如 INT_MAX 表示无法凑成。接下来我们遍历每种硬币 coins[i] 对于每种硬币我们从小到大遍历金额 j 如果 j coins[i] 说明我们可以用这种硬币来凑成金额 j 那么我们就比较使用这种硬币和不使用这种硬币的结果取最小值即 dp[j] min(dp[j], dp[j - coins[i]] 1) 。注意这里和 01 背包问题的区别01 背包问题中只能用一次每种物品所以要从大到小遍历金额避免重复使用而完全背包问题中可以用无限次每种物品所以要从小到大遍历金额允许重复使用。最后我们返回 dp[amount] 即凑成总金额所需的最少硬币个数。如果这个值等于 INT_MAX 说明无法凑成返回 -1 否则返回这个值。 具体实现 这个代码和上一个代码的区别在于它只用了一个一维数组来存储状态值而不是一个二维数组。这样做的原因是对于每种硬币我们只需要知道上一行的状态值就可以更新当前行的状态值所以我们可以用一个一维数组来代替二维数组节省空间。我们可以用一个嵌套的循环来实现上述算法思路外层循环遍历硬币种类内层循环遍历金额。每次更新 dp[j] 时先判断是否可以使用当前硬币并更新为最小值。我们还需要注意一些边界情况比如当金额为零时返回零当硬币数组为空时返回 -1 。 class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for (int i 0; i coins.size(); i) {for (int j 0; j amount; j) {if (j coins[i] dp[j - coins[i]]!INT_MAX) {dp[j] min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount] INT_MAX? -1 : dp[amount];}
};算法分析 时间复杂度O(N*M)其中 N 是硬币种类数M 是总金额。我们需要遍历所有的硬币和金额组合每次更新一个状态值。空间复杂度O(M)其中 M 是总金额。我们只需要一个一维数组来存储状态值。
三、注意
这道题不在乎硬币是排列还是组合是因为我们只关心最少的硬币个数而不关心硬币的顺序。换句话说我们只要找到一种硬币组合使得它的总金额等于目标金额并且硬币个数最少那么这种组合就是最优解无论它的硬币顺序如何。例如如果目标金额是 11 硬币面额是 [1, 2, 5] 那么无论是 [5, 5, 1] 还是 [1, 5, 5] 都是最优解因为它们都只用了 3 个硬币。所以不需要考虑排列和组合的区别只需要考虑状态转移的逻辑。
