当前位置: 首页 > news >正文

2024.3.25力扣每日一题——零钱兑换2

2024.3.25

      • 题目来源
      • 我的题解
        • 方法一 动态规划

题目来源

力扣每日一题;题序:518

我的题解

方法一 动态规划

给定总金额 amount 和数组 coins,要求计算金额之和等于 amount 的硬币组合数。其中,coins的每个元素可以选取多次,且不考虑选取元素的顺序,因此这道题需要计算的是选取硬币的组合数。
可以通过动态规划的方法计算可能的组合数。用 dp[x]表示金额之和等于 x的硬币组合数,目标是求 dp[amount]。
动态规划的边界是 dp[0]=1。只有当不选取任何硬币时,金额之和才为 0,因此只有 1 种硬币组合。
对于面额为 coin 的硬币,当 coin≤i≤amount时,如果存在一种硬币组合的金额之和等于 i−coin,则在该硬币组合中增加一个面额为 coin的硬币,即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins,对于其中的每一种面额的硬币,更新数组 dp中的每个大于或等于该面额的元素的值。

时间复杂度:O(Sn)。S是需要匹配的金额,n为面额数
空间复杂度:O(S)

    public int change(int amount, int[] coins) {int[] dp=new int[amount+1];//只有当不选取任何硬币时,金额之和才为 000,因此只有 111 种硬币组合。dp[0]=1;//因为外层循环是遍历数组 coins 的值,内层循环是遍历不同的金额之和,在计算 dp[i]的值时,可以确保金额之和等于 i 的硬币面额的顺序,由于顺序确定,因此不会重复计算不同的排列。for(int coin:coins){for(int i=coin;i<=amount;i++){dp[i]+=dp[i-coin];}}return dp[amount];}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

相关文章:

2024.3.25力扣每日一题——零钱兑换2

2024.3.25 题目来源我的题解方法一 动态规划 题目来源 力扣每日一题&#xff1b;题序&#xff1a;518 我的题解 方法一 动态规划 给定总金额 amount 和数组 coins&#xff0c;要求计算金额之和等于 amount 的硬币组合数。其中&#xff0c;coins的每个元素可以选取多次&#…...

包子凑数【蓝桥杯】/完全背包

包子凑数 完全背包 完全背包问题和01背包的区别就是&#xff0c;完全背包问题每一个物品能取无限次。 思路&#xff1a;当n个数的最大公约数不为1&#xff0c;即不互质时&#xff0c;有无限多个凑不出来的&#xff0c;即n个数都可以表示成kn&#xff0c;k为常数且不为1。当n个…...

口语 4.6

drop the gun :逃避 radically 极大程度地 vastly cognition&#xff1a;认知能力 flaw缺陷 flawless&#xff1a;没有缺陷 interface&#xff1a;接口&#xff0c;交流处 retain&#xff1a;保留 down the rabbit hole&#xff1a;进入未知领域了 wrap your head aro…...

使用Docker 部署jenkins 实现自动化部署

使用Docker部署jenkins实现自动化部署ruoyi-vue docker jenkinsJava jenkinsfilevue jenkinsfileDockerfile 部署脚本Java Dockerfilenginx Dockerfilenginx-dev.conf 使用docker部署Jenkins&#xff0c;项目: https://gitee.com/y_project/RuoYi-Vue 作为部署项目示范 docker…...

golang语言系列:Web框架+路由 之 Gin

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言学习系列&#xff0c;本篇对Gin框架的基本使用方法进行学习 1.Gin框架是什么 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者…...

春招百题--堆

一、堆的定义 二、堆&#xff08;优先队列&#xff09; 堆通常用于实现优先队列&#xff08;priority_queue&#xff09;&#xff0c;大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看&#xff0c;我们可以将“优先队列”和“堆”看作等价的数据结构。 堆的…...

全志A40i android7.1 移植wifi驱动的一般流程

一&#xff0c;问题分析 一般情况下移植一款模组&#xff0c;会涉及到驱动&#xff0c;firmware, hal层&#xff0c;方案端的适配。 下面以RTL8723ds为例详细列出移植的通用步骤。 二&#xff0c;移植步骤 1. 移植Wi-Fi驱动 从RTL原厂或者已经支持的其他把内核版本中获取驱动…...

Qt——Qt绘图之QPainter的使用总结(使用paintEvent实现旋转图片效果)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...

Day83:服务攻防-开发组件安全JacksonFastJson各版本XStreamCVE环境复现

目录 J2EE-组件Jackson-本地demo&CVE 代码执行 (CVE-2020-8840) 代码执行 (CVE-2020-35728&#xff09; J2EE-组件FastJson-本地demo&CVE FastJson < 1.2.24 FastJson < 1.2.47 FastJson < 1.2.80 (利用条件比较苛刻) J2EE-组件XStream-靶场&CVE …...

【QT+QGIS跨平台编译】056:【pdal_kazhdan+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

点击查看专栏目录 文章目录 一、pdal_kazhdan介绍二、pdal下载三、文件分析四、pro文件五、编译实践一、pdal_kazhdan介绍 pdal_kazhdan 是 PDAL(Point Data Abstraction Library)相关的 Kazhdan 算法的实现。PDAL 是一个用于处理和分析点云数据的开源库,而 Kazhdan 算法通常…...

泰坦尼克号幸存者数据分析

泰坦尼克号幸存者数据分析 1、泰坦尼克号数据集2、数据集加载与概览3、泰坦尼克号幸存者数据分析4、哪些人可能成为幸存者&#xff1f; 1、泰坦尼克号数据集 泰坦尼克号的沉没是世界上最严重的海难事故之一&#xff0c;造成了大量的人员伤亡。这是一艘号称当时世界上最大的邮轮…...

Memcached 教程之 PHP 连接 Memcached 服务(十)

PHP 连接 Memcached 服务 在前面章节中我们已经介绍了如何安装 Memcached 服务&#xff0c;接下来我们为大家介绍 PHP 如何使用 Memcached 服务。 PHP Memcache 扩展安装 PHP Memcache 扩展包下载地址&#xff1a;PECL :: Package :: memcache&#xff0c;你可以下载最新稳定…...

【zlm】音视频流与音频流合并的设计

目录 设想一 设想二 方案三 关键技术 测试语句 测试脚本 参考文档 设想一 //开始录制_option.mp4_save_path custom_path;_option.mp4_max_second max_second;vector<Track::Ptr> mytracks getTracks();auto src MediaSource::find( DEFAULT_VHOST, "1&quo…...

typescript的工作流

先coding code.ts代码&#xff0c;由tsc编译code.ts生成code.js格式 npm install —save-dev lite-server 是用来安装轻量级的服务器&#xff0c;只是用来开发的一个服务器&#xff0c;真正到生产环境中时可能会使用类似于Apache的server或者汤姆猫一类的服务器&#xff0c;安…...

MATLAB下载与安装详细教程:从官方获取到成功启动

引言 MATLAB&#xff08;MATrix LABoratory&#xff09;作为一款全球知名的高级数值计算与数据分析平台&#xff0c;以其强大的矩阵运算能力、丰富的内置函数库以及直观易用的图形用户界面&#xff0c;深受科研人员、工程师和学生群体的青睐。无论是进行复杂的数学建模、信号处…...

【随笔】Git 高级篇 -- 分离 HEAD(十一)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…...

mac、windows 电脑安装使用多个版本的node

我们为啥要安装多个不同版本的node&#xff1f; 开发旧项目时&#xff0c;使用低版本Nodejs。开发新项目时&#xff0c;需使用高版本Node.js。可使用n同时安装多个版本Node.js&#xff0c;并切换到指定版本Node.js。 mac电脑安装 一、全局安装 npm install -g n 二、mac电脑…...

vue 浅解watch cli computed props ref vue slot axios nexttick devtools说明使用

Vue.js 是一个强大的前端框架&#xff0c;它提供了很多有用的功能和工具。你提到的这些特性&#xff08;watch、cli、computed、props、ref、slot、axios、nextTick、devtools&#xff09;在 Vue 中各自扮演着不同的角色。下面我会逐一解释这些特性如何在 Vue 中使用&#xff1…...

Unity自定义框架(1)-----------单例模式

前言&#xff1a; Unity作为一款强大的游戏开发引擎&#xff0c;其基础框架的设计对于项目的结构和性能有着重要的影响。其中&#xff0c;单例模式是一种常用的设计模式&#xff0c;用于确保一个类只有一个实例&#xff0c;并提供一个全局访问点。 什么是单例模式&#xff1f…...

04-自媒体文章-自动审核

自媒体文章-自动审核 1)自媒体文章自动审核流程 1 自媒体端发布文章后&#xff0c;开始审核文章 2 审核的主要是审核文章的内容&#xff08;文本内容和图片&#xff09; 3 借助第三方提供的接口审核文本 4 借助第三方提供的接口审核图片&#xff0c;由于图片存储到minIO中&…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》

近日&#xff0c;嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》&#xff0c;海云安高敏捷信创白盒&#xff08;SCAP&#xff09;成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天&#xff0c;网络安全已成为企业生存与发展的核心基石&#xff0c;为了解…...