leetcode—— 动态规划—— 零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5]amount = 11输出:3解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2]amount = 3输出:-1
思想:动态规划
边界条件:dp[0] = 0
状态转移方程:F(i) = min j=0,1...nF(i-cj) + 1
定义 F(i)为组成金额 i所需最少的硬币数量,假设在计算 F(i) 之前,我们已经计算出 F(0) ~F(i−1)
的答案,其中 cj代表的是第 j枚硬币的面值
代码:
class Solution {public int coinChange(int[] coins, int amount) {// 初始化动态规划数组 初始化最大值数组int max = amount + 1;int[] dp = new int[amount + 1]; // 数组长度最大为amount+1的原因为: 最坏情况amount= 1+1+...1// 动态规划数组中填充最大值Arrays.fill(dp,max);dp[0] = 0;// 从1开始遍历目标数值for(int i = 1; i <= amount; i++){// 遍历整数数字coins 判断数组中当前面面值是否能组成amountfor(int j = 0; j < coins.length; j++){// 如果当前数组中面值小于i 进行递归计算 (动态规划方程)if(coins[j] <= i){dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1) ;}}}return dp[amount] > amount ? -1 : dp[amount];}
}
相关文章:
leetcode—— 动态规划—— 零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示…...
java面试题(spring框架篇)(黑马 )
树形图: 一、Spring框架种的单例bean是线程安全吗? Service Scope("singleton") public class UserServiceImpl implements UserService{ } singleton:bean在每个Spring IOC容器中只有一个实例 protype:一个bean的定义可以有多个…...
LeetCode27 移除元素
题目 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后…...
自测-5 Shuffling Machine(python版本)
文章预览: 题目翻译算法python代码oj反馈结果 题目 翻译 shuffle是用于随机化一副扑克牌的过程。由于标准的洗牌技术被认为是薄弱的,并且为了避免员工通过不适当的洗牌与赌徒合作的“内部工作”,许多赌场使用了自动洗牌机。你的任务是模拟一…...
你真的会设计测试用例吗?
前言 最近干的最多的事情就是设计测试用例、评审测试用例了,于是我不禁又想到了一个经典的问题:如何设计出优秀的测试用例? 可能有些童鞋看到这个问题会有些不以为然,这有什么好想的?干个测试谁还不会设计测试用例&a…...
外贸网站模板建站
测绘检测wordpress外贸主题 简洁实用的wordpress外贸主题,适合做测绘检测仪器设备的外贸公司使用。 https://www.jianzhanpress.com/?p5337 白马非马衣服WordPress外贸建站模板 白马非马服装行业wordpress外贸建站模板,适用于时间服装企业的官方网站…...
多点通信与域套接字:2024/3/4
作业1:广播 发送端: #include <myhead.h> int main(int argc, const char *argv[]) {//1.创建套接字int sfdsocket(AF_INET,SOCK_DGRAM,0);if(sfd-1){perror("socket error");return -1;}printf("sfd%d\n",sfd);//2.设置当前…...
52.2k star! 自己部署gpt4free, 免费使用各种GPT
GPT4Free是一个由开发者Xtekky在GitHub上发布的开源项目,它可以免费地使用GPT-3.5、GPT-4、llama、gemini-pro、bard、claude等多种大模型。截止到当前(2024.1.30)已经有52.2k star,可见其受欢迎程度。 github地址:https://github.com/xtekky…...
【HbuilderX】 uniapp实现 android申请权限 和 退出app返回桌面
目录 android申请权限: 监听用户是否开启权限或关闭权限: 退出app返回桌面: android申请权限: 首先在 manifest.json 内添加你所需要用到权限 添加权限插件 permission.js 一次就好1/权限插件 - Gitee.comhttps://gitee.co…...
计算机网络之传输层 + 应用层
.1 CIDR地址块中还有三个特殊的地址块 a. 前缀 n 32 , 即32位IP地址都是前缀, 没有主机号, 这其实就是一个IP地址, 用于主机路由 b. 前缀 n 31 , 这个地址块中有两个IP地址, 主机号分别为0/1 , 这个地址块用于点对点链路 c. 前缀 n 0 , 用于默认路由使用二叉线索树查找转发…...
五、软考-系统架构设计师笔记-信息安全技术基础知识
信息安全技术基础知识 1、信息安全基础知识概述 信息安全的概念 信息安全包括 5 个基本要素: 机密性:确保信息不暴露给未授权的实体或进程。完整性:只有得到允许的人才能修改数据,并且能够判别出数据是否已被篡改。可用性:得到授权的实体在需要时可以…...
vue3+uniapp在微信小程序实现一个2048小游戏
一、效果展示 二、代码 <template><view class"page"><view class"top"><view class"score">得分:{{total}}</view><view class"time">用时:{{allTime}}s</view></view><view cl…...
常见的浏览器跨域解决方法
1. 前端方法:JSONP(仅适用于GET请求) JSONP(JSON with Padding)是一种利用<script>标签的src属性不受同源策略限制的特性来实现跨域数据请求的方法。JSONP通过在前端动态创建<script>标签,并将…...
飞桨模型转ONNX模型教程
文章目录 飞桨模型转ONNX模型教程1. ONNX简介2. Paddle2ONNX安装3. 获取Paddle2ONNX模型库4. 飞桨转ONNX教程4.1 飞桨训练模型导出为ONNX模型4.2 飞桨部署模型转为ONNX模型4.3 验证ONNX模型4.4 使用ONNX模型进行推理 5. 注意事项 飞桨模型转ONNX模型教程 1. ONNX简介 ONNX是一…...
vue使用swiper(轮播图)-真实项目使用
一、安装 我直接安装的vue-awesome-swiper": "^3.1.3"指定版本 npm install vue-awesome-swiper3.1.3 swiper --save二、vue页面使用,写了一个小demo <template><div class"vue-swiper"><h1>{{ msg }}</h1><…...
C++ 创建并初始化对象
创建并初始化C对象 当我们创建一个C对象时,它需要占用一些内存,即使我们写一个完全为空的类,类中没有成员,什么也没有,它至少也要占用一个字节的内存。但是我们类中有很多成员,它们需要存储在某地方&#…...
大数据可视化python01
import pandas as pd import matplotlib.pyplot as plt# 设置中文改写字体 plt.rcParams[font.sans-serif] [SimHei]# 读取数据 data pd.read_csv(C:/Users/wzf/Desktop/读取数据进行数据可视化练习/实训作业练习/瓜果类单位面积产量.csv ,encoding utf-8)#输出 print(data)…...
Java底层自学大纲_分布式篇
分布式专题_自学大纲所属类别学习主题建议课时(h)A 分布式锁001 Zookeeper实现分布式锁l-常规实现方式2.5A 分布式锁002 Zookeeper实现分布式锁II-续命&超时&羊群效应问题解决方案2.5A 分布式锁003 Zookeeper实现分布式锁III-基于Curator框架实现…...
Thread多线程(创建,方法,安全,通信,线程池,并发,并行,线程的生命周期)【全详解】
目录 1.多线程概述 2.多线程的创建 3.Thread的常用方法 4.线程安全 5.线程同步 6.线程通信 7.线程池 8.其它细节知识:并发、并行 9.其它细节知识:线程的生命周期 1.多线程概述 线程是什么? 线程(Thread)是一个程序内部的一条执行…...
自定义View中的ListView和ScrollView嵌套的问题
当我们在使用到ScrollView和ListView的时候可能会出现显示不全的问题。那我们可以进行以下分析 ScrollView在测量子布局的时候会用UNSPECIFIED。通过源码观察, 在ScrollView的onMeasure方法中 Overrideprotected void onMeasure(int widthMeasureSpec, int heightMe…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
