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…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...
简单介绍C++中 string与wstring
在C中,string和wstring是两种用于处理不同字符编码的字符串类型,分别基于char和wchar_t字符类型。以下是它们的详细说明和对比: 1. 基础定义 string 类型:std::string 字符类型:char(通常为8位)…...
【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项
一、条形码识别改名使用教程 打开软件并选择处理模式:打开软件后,根据要处理的文件类型,选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件,就选择 “PDF 识别模式”;若是处理图片文件&…...
