零钱兑换,凑零钱问题,从暴力递归到动态规划(java)
凑零钱问题,从暴力递归到动态规划
- leetcode 322 题 零钱兑换
- 暴力递归(这个会超时,leetcode 跑不过去)
- 递归+缓存
- 动态规划优化暴力递归
- 动态规划专题
leetcode 322 题 零钱兑换
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 <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
暴力递归(这个会超时,leetcode 跑不过去)
解题思路:
凑零钱就是每次选择一种面值的零钱后,然后递归下面所有选择的可能,
我们去递归遍历所有可能性,然后选择一个最少的可能。
代码演示:
int coinChange(int[] coins, int amount) {if(amount == 0){return 0;}return process(coins,amount);}public int process(int[]coins,int amount){//base caseif(amount == 0){return 0;}//base case if(amount < 0){return -1;}int res = Integer.MAX_VALUE;for(int c : coins){int num = process(coins,amount - c);//当前这种情况无法完成,继续递归if(num == -1){continue;}//比较更新保存最小值res = Math.min(res,num + 1);}return res == Integer.MAX_VALUE ? -1 : res;}

递归+缓存
思路:
缓存就是为了减少重复计算,这里面的重复计算,很明显就是剩余要凑出来的零钱。
用数组进行缓存。
对上面暴力递归 稍加改造
代码演示
class Solution {int[]ans;int coinChange(int[] coins, int amount) {if(amount == 0){return 0;} ans = new int[amount + 1];return process(coins,amount);}public int process(int[]coins,int amount){if(amount == 0){return 0;}if(amount < 0){return -1;}if(ans[amount] != 0){return ans[amount];}int res = Integer.MAX_VALUE;for(int c : coins){int num = process(coins,amount - c);if(num == -1){continue;}res = Math.min(res,num + 1);}ans[amount] = res == Integer.MAX_VALUE ? -1 : res;return ans[amount];}
}

动态规划优化暴力递归
动态规划是自底向上的求出所有值,保存在缓存里,然后去拿,
这个和递归加缓存的区别就是,第二种还是自顶向下计算,缓存只是为了去除重复计算,
动态规划则是直接把整个缓存表都填满,需要什么去拿什么
之所以这样,是为了更难的题,有了这个表格后,可以做很多操作,
就目前这个题,递归加缓存和动态规划并没有实质的提升.
代码:
int coinChange(int[] coins, int amount) {int[]dp = new int[amount + 1];//初始化为amount + 1 因为最大值也就是amount 全是一元凑出来。Arrays.fill(dp, amount + 1);//base case dp[0] = 0;for(int i = 0; i < dp.length;i++){for(int coin : coins){if(i - coin < 0){continue;}dp[i] = Math.min(dp[i] ,dp[i - coin] + 1);}}return (dp[amount] == amount + 1) ? -1 : dp[amount];}

动态规划专题
斐波那契数列-从暴力递归到动态规划
走到指定位置有多少种方式-从暴力递归到动态规划
相关文章:
零钱兑换,凑零钱问题,从暴力递归到动态规划(java)
凑零钱问题,从暴力递归到动态规划 leetcode 322 题 零钱兑换暴力递归(这个会超时,leetcode 跑不过去)递归缓存动态规划优化暴力递归动态规划专题 leetcode 322 题 零钱兑换 322 零钱兑换 - 可以打开链接测试 给你一个整数数组 c…...
Vue登录界面精美模板分享
文章目录 🐒个人主页🏅Vue项目常用组件模板仓库📖前言:🎀源码如下: 🐒个人主页 🏅Vue项目常用组件模板仓库 📖前言: 本篇博客主要提供vue组件之登陆组件源码…...
Linux设备驱动程序(二)——建立和运行模块
文章目录 前言一、设置测试系统二、Hello World 模块1、代码详解2、执行效果 三、内核模块相比于应用程序1、用户空间和内核空间2、内核的并发3、当前进程4、几个别的细节 四、编译和加载1、编译模块2、加载和卸载模块3、版本依赖 五、内核符号表六、预备知识七、初始化和关停1…...
【算法】单调栈问题
文章目录 题目思路分析代码实现 题目 给定一个不含有重复值的数组arr,找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置,返回所有位置相应的消息。 比如arr{3,4,1,5,6,2,…...
Hack The Box - 关卡Dancing
SMB(全称是Server Message Block)是一个协议名,可用于在计算机间共享文件、打印机、串口等,电脑上的网上邻居就是靠它实现的。 SMB 是一种客户机/服务器、请求/响应协议。通过 SMB 协议,客户端应用程序可以在各种网络环境下读、写服务器上的…...
【软件设计与体系结构】 软件体系结构风格
软件体系结构(Software Architecture) 软件体系结构(Software Architecture)包括构成系统的设计元素的描述、 设计元素 之间的交互、 设计元素的组合模式以及在这些模式中的约束。 定义 软件体系结构表示系统的框架结构…...
detectron2 使用教程
本范例演示使用非常有名的目标检测框架detectron2 🤗🤗 在自己的数据集(balloon数据)上训练实例分割模型MaskRCNN的方法。 detectron2框架的设计有以下一些优点: 1,强大:提供了包括目标检测、实例分割、全景分割等非常广泛的视觉任务模型库。 2,灵活:可以通过注册机…...
哈希表常用数据结构
哈希表常用数据结构 查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。 哈希法也是空间换时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。 集合底层实现…...
Java字节流
4 字节流 字节流抽象基类 InputStream:这个抽象类是表示字节输入流的所有类的超类OutputStream:这个抽象类是表示字节输出流的所有类的超类子类名特点:子类名称都是以其父类名作为子类名的后缀4.1 IO流概述和分类 IO流概述: IO: 输入/输出(Input/Output)流:是一种抽象概念…...
arm3399主板-使用ubuntu20.04搭建LVS-DR(netplan)
目录 一、规划 1、网络拓扑 2、检查 二、配置设备 1、配置LVS 1.配置IP转发 2.清除防火墙 3.安装ipvsadm工具 4.配置VIP 5.netplan与NetworkManager介绍 6.添加LVS规则 1.清除防火墙 2.添加伪装IP 3.安装web服务 4. 修改内核参数,防止IP冲突 3、配置w…...
Go中同/异步与锁的应用~~sync包
Go中锁的实现~~sync包 go中sync包中提供了互斥锁; 在前面Go中channel文章中我们使用了time.Sleep()函数使得main函数的Goroutine阻塞至所有协程Goroutine结束,但这并不是一个很好的办法,因为我们实际应用中并不能准确知道协程什么时候结束(这里面要考虑服务器的性能,网络波动以…...
Flask知识点2
1、flash() get_flashed_messages() : 用来消耗flash方法中存储的消息 使用flash存储消息时,需要设置SECRET_KEY flash 内部消息存储依赖了session 2、CSRF(Cross Site Request Forgery) 跨站请求伪造,指攻击者盗用你的身份发送恶意请求 CSRFProt…...
R语言生物群落(生态)数据统计分析与绘图(从数据整理到分析结果展示)
R 语言作的开源、自由、免费等特点使其广泛应用于生物群落数据统计分析。生物群落数据多样而复杂,涉及众多统计分析方法。以生物群落数据分析中的最常用的统计方法回归和混合效应模型、多元统计分析技术及结构方程等数量分析方法为主线,通过多个来自经典…...
代码随想录训练营Day58| 739. 每日温度 496.下一个更大元素 I
目录 学习目标 学习内容 739. 每日温度 496.下一个更大元素 I 学习目标 739. 每日温度 496.下一个更大元素 I 学习内容 739. 每日温度 739. 每日温度 - 力扣(LeetCode)https://leetcode.cn/problems/daily-temperatures/ class Solution:def da…...
设计模式-命令模式
命令模式 问题背景命令模式基本介绍UML类图 解决方案UML类图代码示例 问题背景 1)随着现在科技越来越先进,我们在家庭中对物品的开关都不需要亲自走过去来进行了。我们只需要通过手机APP中的按键来远程执行这个命令。 2)其实这就是命令模式&…...
软考——下午题部分,例题一,二,三,六
例题一 11年上半年 病人,护理人员,医生 D 生命体征范围文件 日志文件 病历文件 治疗意见文件 14年上 E1 巴士司机,2 机械师,3 会计,4 主管,5 库存管理系统 D 巴士列表文件 维修记录文件 部件清单 人事档案 14年下 1 客户 2 供应商 D 销售订单表 库存…...
关于render: h => h(App)的解释
当我们第一次安装完脚手架,打开 的时候,我相信,一定有小伙伴和我一样,看到main.js里面的render: h > h(App),感觉懵懵的。 因为,在刚开始接触vue的时候,我们这里是这样写的: 而使用了脚手…...
flask实现简易图书管理系统
项目结构 技术选型 flask 做后端, 提供数据和渲染html 暂时没有提供mysql, 后续会更新操作mysql和样式美化的版本 起一个flask服务 flask是python的一个web框架, 下面演示如何提供http接口, 并返回json数据 main.py # flask创建http接口 from flask import Flask, request, jso…...
2021 年全国大学生物联网设计竞赛(华为杯)全国总决赛获奖名单
由全国高等学校计算机教育研究会主办,上海交通大学承办,华为技术有限 公司协办,中国电信天翼物联、中国移动中移物联网、霍尼韦尔 Tridium、CSA 联盟、新大陆、德州仪器 (TI)、百度、机械工业出版社华章公司联合支持的 2021 全国大学生物联网…...
操作系统复习2.3.5-管程
引入管程 PV操作困难,容易书写出错,引入管程,作为一种高级同步机制 组成 局限于管程的共享数据结构说明对该数据结构进行操作的一组过程对局部于管程的共享数据结构设置初始值的语句管程有一个名字 基本特征 局限于管程的数据只能被局限…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果