leetcode322. 零钱兑换
给你一个整数数组 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 <= 12
1 <= coins <= 231 - 1
0 <= amount <= 104
标题形貌
给定一组货币面额和一个总金额，盘算可以凑出该总金额的硬币组合数。如果没有任何一种组合可以凑出该金额，则返回 -1。
算法分析
这个题目可以通过动态规划来办理。我们创建一个数组 dp，此中 dp[j] 体现凑出金额 j 的最小硬币数量。我们遍历全部大概的硬币组合，并更新 dp 数组。
算法步调
- 初始化一个数组 dp，其巨细为 amount + 1，全部元素初始化为无穷大，除了 dp[0] 初始化为 0。
- 遍历全部大概的硬币组合。
- 对于每个硬币 coins，更新 dp[j] 为 min(dp[j], dp[j - coins] + 1)，此中 j 是当前思量的金额。
- 末了，查抄 dp[amount] 是否为无穷大。如果是，则没有有用的组合；否则，返回 dp[amount]。
算法流程
具体代码
- //dp[j] = min(dp[j], dp[j - coins[i]] + 1)
- class Solution {
- public:
- int coinChange(vector<int>& coins, int amount) {
- vector<int> dp(amount + 1, INT_MAX/2);
- dp[0] = 0;
- for (int i = 0; i < coins.size(); ++i) {
- for (int j = 1; j <= amount; ++j) {
- if (coins[i] <= j) {
- dp[j] = min(dp[j], dp[j - coins[i]] + 1);
- }
- }
- }
- return dp[amount] == INT_MAX/2 ? -1 : dp[amount];
- }
- };
复杂度分析
- 时间复杂度：O(amount * coins.size())，此中 amount 是总金额，coins.size() 是硬币种类的数量。
- 空间复杂度：O(amount)，我们须要一个数组来存储每个金额的最小硬币数量。
易错点
- 在初始化 dp 数组时，确保全部元素都被精确初始化。
- 在更新 dp 数组时，确保精确土地算最小硬币数量。
- 在查抄是否有有用组适时，确保精确地处置惩罚无穷大的情况。
留意事项
- 确保在遍历硬币组适时不要超出数组的边界。
- 在处置惩罚数组时，确保不会覆盖任何元素。
相似标题
标题链接零钱兑换https://leetcode.com/problems/coin-change/最大子序和https://leetcode.com/problems/maximum-subarray/最长递增子序列https://leetcode.com/problems/longest-increasing-subsequence/最小路径和https://leetcode.com/problems/minimum-path-sum/背包题目模板
背包分类：
1、0/1背包：外循环nums,内循环target,target倒序且target>=nums;
2、完全背包：外循环nums,内循环target,target正序且target>=nums;
题目分类：
1、最值题目:
dp = max/min(dp, dp[i-nums]+1);
或
dp = max/min(dp, dp[i-num]+nums);
2、存在题目(bool)：
dp=dp||dp[i-num];
3、组合题目：
dp+=dp[i-num];
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金 |
发表于 