力扣第322题 零钱兑换 c++ java 动态规划
题目
322. 零钱兑换
中等
相关标签
广度优先搜索 数组 动态规划
给你一个整数数组 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数组的定义:代码创建了一个大小为amount+1的dp数组,用于保存计算中间状态的结果。dp[i]表示组成金额i所需的最少硬币数量。初始化:将
dp[0]初始化为 0,表示组成金额为 0 不需要任何硬币。其他位置的dp数组元素初始化为INT_MAX,表示初始时无法凑出对应的金额。状态转移方程:采用两层循环来遍历物品和背包。外层循环遍历所有可用的硬币面额,内层循环遍历目标金额从该硬币面额开始到
amount。这样可以逐步更新dp数组,计算得到凑出每个目标金额所需的最少硬币数量。状态转移:对于当前的目标金额
j,我们检查dp[j - coins[i]]是否不是初始值INT_MAX。如果不是初始值,则表示可以通过使用当前硬币面额coins[i]得到目标金额j。我们比较使用当前硬币和不使用当前硬币两种情况下所需的硬币数量,并取最小值作为dp[j]的解。返回结果:最后,我们返回
dp[amount]的值作为结果。如果dp[amount]仍为初始值INT_MAX,表示无法凑出目标金额,因此返回 -1。总结起来,这段代码使用动态规划的思想,通过构建一个
dp数组来保存计算中间状态的结果。通过遍历物品和背包,并利用已解决子问题的解,逐步计算得到组成目标金额所需的最少硬币数量。最终,返回dp[amount]的值作为结果。
复杂度
时间复杂度:
O(n * amount)
时间复杂度:
- 外层循环遍历硬币列表的长度,即
coins的大小,所以时间复杂度为 O(n),其中 n 是硬币列表的长度。- 内层循环遍历目标金额
amount,所以时间复杂度为 O(amount)。综合起来,总的时间复杂度为 O(n * amount)。
空间复杂度
O(amount)
空间复杂度:
- 创建了一个大小为
amount+1的dp数组,所以空间复杂度为 O(amount)。因此,该算法的空间复杂度为 O(amount)。
c++ 代码
class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX); // 创建大小为 amount+1 的 dp 数组,初始值设置为 INT_MAXdp[0] = 0; // 对于组成金额为 0 的情况,方法数为 0for (int i = 0; i < coins.size(); i++) { // 遍历每个硬币面额(物品)for (int j = coins[i]; j <= amount; j++) { // 遍历每个目标金额(背包)if (dp[j - coins[i]] != INT_MAX) { // 如果 dp[j - coins[i]] 不是初始值(即存在组合方式)dp[j] = min(dp[j - coins[i]] + 1, dp[j]); // 更新组成金额 j 的最小方法数}}}if (dp[amount] == INT_MAX) return -1; // 如果无法组成金额 amount,则返回 -1 表示无解return dp[amount]; // 返回组成金额 amount 的最小方法数}
};
vector<int> dp(amount + 1, INT_MAX);:创建大小为 amount+1 的 dp 数组,用于保存组成不同金额的最小硬币数。初始值设置为 INT_MAX,表示初始状态下无解。dp[0] = 0;:对于金额为 0 的情况,不需要使用任何硬币,所以最小硬币数为 0。for (int i = 0; i < coins.size(); i++):外层循环遍历硬币面额(物品),以便逐个考虑每个硬币的组合方式。for (int j = coins[i]; j <= amount; j++):内层循环遍历目标金额(背包),从当前硬币面额开始,直到目标金额 amount。这样可以确保只考虑能够达到的金额。if (dp[j - coins[i]] != INT_MAX):如果 dp[j - coins[i]] 不是初始值(即存在组合方式),则进入条件判断。dp[j] = min(dp[j - coins[i]] + 1, dp[j]);:更新组成金额 j 的最小硬币数。在当前硬币面额 coins[i] 的情况下,组成金额 j 的最小硬币数为 dp[j - coins[i]] + 1 和当前 dp[j] 的较小值。if (dp[amount] == INT_MAX) return -1;:如果无法组成金额 amount,则返回 -1 表示无解。return dp[amount];:返回组成金额 amount 的最小硬币数。
Java代码
class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount + 1];//初始化dp数组为最大值for (int j = 0; j < dp.length; j++) {dp[j] = max;}//当金额为0时需要的硬币数目为0dp[0] = 0;for (int i = 0; i < coins.length; i++) {//正序遍历:完全背包每个硬币可以选择多次for (int j = coins[i]; j <= amount; j++) {//只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要if (dp[j - coins[i]] != max) {//选择硬币数目最小的情况dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == max ? -1 : dp[amount];}
}
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
相关文章:
力扣第322题 零钱兑换 c++ java 动态规划
题目 322. 零钱兑换 中等 相关标签 广度优先搜索 数组 动态规划 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组…...
uniapp 子组件内使用定时器无法清除
涉及到的知识点:1.ref绑定在组建上获取组件实例。2.emit逆向传值,不需要点击触发,watch监听即可。 需求:在父页面的子组件定时发送请求,离开父页面就停止,再次进入就开启。 问题:在父页面的子…...
加载动态库的几种方式
静态加载、动态加载和延迟加载 dll加载方式大致可以分为3类:静态加载、动态加载和延迟加载 1.静态加载,dll的加载发生在程序main函数启动前。 2.动态加载,使用LoadLibrary或者LoadLibraryEx来加载一个dll。当dll加载成功时,你会…...
视频转序列图片:掌握技巧,轻松转换
随着社交媒体和视频平台的日益普及,视频已成为我们生活中不可或缺的一部分。有时,我们需要将视频转换为图片序列,例如制作GIF动图或提取视频中的特定画面。现在一起来看云炫AI智剪如何将视频转换为序列图片,并轻松实现转换。 操作…...
python 数据挖掘库orange3 介绍
orange3 是一个非常适合初学者的data mining library. 它让使用者通过拖拽内置的组件来形成工作流。让你不需要写任何代码就可以体验到数据挖掘和可视化的魅力。 它的桌面如下,这里我创建了 3 个节点,分别是数据集、小提琴图,散点图 其中 …...
Android和JNI交互 : 常见的图像格式转换 : NV21、RGBA、Bitmap等
1. 前言 最近在使用OpenCV处理图片的时候,经常会遇到需要转换图像的情况,网上相关资料比较少,也不全,有时候得费劲老半天才能搞定。 自己踩了坑后,在这里记录下,都是我在项目中遇到的图像转化操作…...
AndroidAuto 解决连接手机启动AA屏闪一下问题
AndroidAuto一般在AndroidManifest.xml注册的Activity配置过滤监听特定手机的USB插拔启动AA <activityandroid:name=".sink.ui.MainActivity"android:configChanges="keyboard|keyboardHidden|uiMode"android:windowSoftInputMode="stateHidden&qu…...
jbase实现业务脚本化
经过晚上和早上的努力,终于补上框架最后一块了,业务脚本侦听变化后自动编译jar包和调用,实现维护成本低,开发效率高的框架的基本体系。 实现自动编译jar包的类 package appcode;import org.w3c.dom.Document; import org.w3c.do…...
【安全】Java幂等性校验解决重复点击(6种实现方式)
目录 一、简介1.1 什么是幂等?1.2 为什么需要幂等性?1.3 接口超时,应该如何处理?1.4 幂等性对系统的影响 二、Restful API 接口的幂等性三、实现方式3.1 数据库层面,主键/唯一索引冲突3.2 数据库层面,乐观锁…...
基于设深度学习的人脸性别年龄识别系统 计算机竞赛
文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习机器视觉的…...
0001Java安卓程序设计-基于Android多餐厅点餐桌号后厨前台服务设计与开发
文章目录 **摘** **要****目** **录**系统设计开发环境 编程技术交流、源码分享、模板分享、网课教程 🐧裙:776871563 摘 要 移动互联网时代的到来,给人们的生活带来了许多便捷和乐趣。随着用户的不断增多,其规模越来越大&#…...
Node.js 中解析 HTML 的方法介绍
在 Web 开发中,解析 HTML 是一个常见的任务,特别是当我们需要从网页中提取数据或操作 DOM 时。掌握 Node.js 中解析 HTML 的各种方式,可以大大提高我们提取和处理网页数据的效率。本文将介绍如何在 Node.js 中解析 HTML。 基本概念 HTML 解析…...
软件开发项目文档系列之十如何撰写测试用例
目录 1 概述1.1 编写目的1.2 定义1.3 使用范围1.4 参考资料1.5 术语定义 2 测试用例2.1 功能测试2.1.1 用户登录功能2.1.2 商品搜索功能 2.2 性能测试2.2.1 网站响应时间2.2.2 并发用户测试 附件: 测试用例撰写的要素和注意事项附件1 测试用例要素附件2 测试用例的注…...
AI:53-基于机器学习的字母识别
🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌本专栏包含以下学习方向: 机器学习、深度学…...
实习记录--(海量数据如何判重?)--每天都要保持学习状态和专注的状态啊!!!---你的未来值得你去奋斗
海量数据如何判重? 判断一个值是否存在?解决方法: 1.使用哈希表: 可以将数据进行哈希操作,将数据存储在相应的桶中。 查询时,根据哈希值定位到对应的桶,然后在桶内进行查找。这种方法的时间复…...
【MATLAB源码-第67期】基于麻雀搜索算法(SSA)的无人机三维地图路径规划,输出最短路径和适应度曲线。
操作环境: MATLAB 2022a 1、算法描述 麻雀搜索算法(Sparrow Search Algorithm, SSA)是一种新颖的元启发式优化算法,它受到麻雀社会行为的启发。这种算法通过模拟麻雀的食物搜索行为和逃避天敌的策略来解决优化问题。SSA通过模…...
Promise的并发控制 - 从普通并发池到动态并发池
一、场景 给你一个有200个URL的数组,通过这些URL来发送请求,要求并发请求数不能超过五个。 这是一道很常考的面试题,接下来让我们来学习一下Promise并发控制 二、普通并发池的实现 主要思路就是,判断当前队列是否满,…...
Java类加载机制(类加载器,双亲委派模型,热部署示例)
Java类加载机制 类加载器类加载器的执行流程类加载器的种类加载器之间的关系ClassLoader 的主要方法Class.forName()与ClassLoader.loadClass()区别 双亲委派模型双亲委派 类加载流程优缺点 热部署简单示例 类加载器 类加载器的执行流程 类加载器的种类 AppClassLoader 应用类…...
【C语言初学者周冲刺计划】3.2将一个数组中的值逆序重新存放
目录 1解题思路: 2代码 3运行代码如图: 4总结: 1解题思路: 首先学会如何利用循环输入位数和输入数值,然后再利用循环逆序即可 2代码 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int main() { int…...
【C++心愿便利店】No.11---C++之string语法指南
文章目录 前言一、 为什么学习string类二、标准库中的string类 前言 👧个人主页:小沈YO. 😚小编介绍:欢迎来到我的乱七八糟小星球🌝 📋专栏:C 心愿便利店 🔑本章内容:str…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...
