首页 > 其他分享 >leetcode322. 零钱兑换,完全背包最值问题,附背包问题模板

leetcode322. 零钱兑换,完全背包最值问题,附背包问题模板

时间:2024-08-20 21:51:06浏览次数:13  
标签:背包 target 硬币 coins amount 最值 数组 leetcode322 dp

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[i] <= 231 - 1
0 <= amount <= 104

在这里插入图片描述

目录

题目描述

给定一组货币面额和一个总金额,计算可以凑出该总金额的硬币组合数。如果没有任何一种组合可以凑出该金额,则返回 -1。

算法分析

这个问题可以通过动态规划来解决。我们创建一个数组 dp,其中 dp[j] 表示凑出金额 j 的最小硬币数量。我们遍历所有可能的硬币组合,并更新 dp 数组。

算法步骤

  1. 初始化一个数组 dp,其大小为 amount + 1,所有元素初始化为无穷大,除了 dp[0] 初始化为 0。
  2. 遍历所有可能的硬币组合。
  3. 对于每个硬币 coins[i],更新 dp[j]min(dp[j], dp[j - coins[i]] + 1),其中 j 是当前考虑的金额。
  4. 最后,检查 dp[amount] 是否为无穷大。如果是,则没有有效的组合;否则,返回 dp[amount]

算法流程

开始 初始化数组 dp 遍历所有可能的硬币组合 更新 dp 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[i];
2、完全背包:外循环nums,内循环target,target正序且target>=nums[i];

问题分类:
1、最值问题:

dp[i] = max/min(dp[i], dp[i-nums]+1);

dp[i] = max/min(dp[i], dp[i-num]+nums);

2、存在问题(bool):

dp[i]=dp[i]||dp[i-num];

3、组合问题:

dp[i]+=dp[i-num];

标签:背包,target,硬币,coins,amount,最值,数组,leetcode322,dp
From: https://blog.csdn.net/qq_51350957/article/details/141326636

相关文章

  • 粒子群算法初步与在求函数最值上的应用
    粒子群算法是一种优化算法,也是一种启发式算法。按照预定的策略实行搜索,在搜索过程中获取的中间信息不用来改进策略,称为盲目搜索;反之,如果利用了中间信息来改进搜索策略则称为启发式搜索。蒙特卡罗模拟用来求解优化问题就是盲目搜索,还有大家熟悉的枚举法也是盲目搜索。因为其并没有......
  • 01背包问题
    有 NN 件物品和一个容量是 VV 的背包。每件物品只能使用一次。第 ii 件物品的体积是 vivi,价值是 wiwi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,VN,V,用空格隔开,分别表示物品数量和背包容积......
  • Codeforces 232 B Table 题解 [ 蓝 ] [ 分组背包 ] [ 组合数学 ] [ 循环节 ]
    Codeforces232BTable。蒟蒻模拟赛上场切的一道蓝,非常难以置信我竟然能做蓝题。这题的数据范围初看还是比较坑的,\(10^{18}\)的值域很容易让人往矩阵加速那方面想。实际上在列出转移方程式后,我们发现状态是二维的,无法使用矩阵加速(或者说这样做很麻烦)。思路首先观察到每个边长......
  • 【动态规划】0/1背包问题
    题目描述有个背包可承受重量N,现有T件物品每件物品重量为Wi,价值为Vi,每件物品只有一个,这个背包可以装载物品的最大价值是多少?输入从文件 beibao1.in 中读入数据。一行两个正整数NT,之间用空格隔开后面T行,每行两个正整数,分别表示重量Wi,价值Vi输出输出到文......
  • 『区间最值操作 & 区间历史最值』Day6
    1势能1.1有一类之前就见过的操作。区间取模区间开方。开方是说在\(\log\logB\)次过后就不变了,所以这之前暴力即可。取模则是说如果一个数能取模那么至少会减少一半,所以一个数最多暴力操作\(\logB\)次就没了。对于一个区间你维护最大值看是否需要递归进行操作即可。上......
  • 贪心法-一般背包问题
    一般背包问题问题描述想象你有一个背包,它最多可以放M公斤的物品。你面前有n个物品,每个物品的重量是Wi,如果将这个物品完全放入背包,你将获得Pi的收益。问题目标你需要决定如何放置这些物品,以便在不超过背包容量的前提下,获得最大的收益。问题类型0/1背包问题:每个......
  • 区间历史最值线段树记录
    Description维护一个线段树,使得可以实现区间加、区间chkmin、求区间最值、区间历史最值、区间最大值。Solution先不考虑区间chkmin和历史最值,可以直接对于每个线段树节点维护一个tag,每次addtag更新。加上区间历史最值后,先考虑对于单个线段树节点怎么更新。容易发现对于......
  • 背包问题 持续更新中!
    背包九讲一、01背包问题题目概览有NNN件物品和一个容量是VVV的背......
  • 动态规划之——背包DP(进阶篇)
    文章目录概要说明多重背包(朴素算法)模板例题思路code多重背包(二进制优化)模板例题思路code多重背包(队列优化)模板例题思路混合背包模板例题思路code1code2二维费用背包模板例题思路code概要说明本文讲多重背包、混合背包以及二维费用背包,至于其他背包问题后续......
  • 想学习人工智能、大语言模型?这份学习路线与免费学习资源最值得推荐
    想学习人工智能吗?但不知道如何开始?要熟练掌握人工智能相关的技术,光学习很多课程是不够的。为了摆脱只是跟着教程学习,你需要亲自动手,从头开始编写算法,动手实践,并通过使用人工智能解决问题来做一些有趣的边项目。这篇文章试图创建一份免费的课程路径,希望对大家学习有帮助。(注......