研习代码 day39 | 动态规划——完全背包的应用
一、爬楼梯(进阶版)
1.1 题目
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
输入描述
输入共一行,包含两个正整数,分别表示n, m
输出描述
输出一个整数,表示爬到楼顶的方法数。
输入示例
3 2
输出示例
3
1.2 题目链接
57.爬楼梯
1.3 解题思路与过程想法
(1)解题思路
# 分析:这道题是 70.爬楼梯 的进阶版,对于每次爬楼的最多阶数是个不定值 n。是个典型的背包的排列问题。
排列问题:1+2+1 和 2+1+1 是两种不同方法
数组:爬到 i 阶,有 dp[i] 种方法
递推关系:求组成的方法数——————dp[j] += dp[j-i],
求背包装载的最大“价值” ——dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
求背包装载的最少“数量” ——dp[j] = min(dp[j], dp[j-weight[i]]+1)
初始化:求组成的方法数——dp[0] = 1
其他值初始化———初始化不影响覆盖的值,求最大-->初始化最小;
求最小-->初始化无穷大值
遍历顺序:因为是排列问题,所以先遍历背包容量,后遍历物体
此处 weight[i] 对应着 本次爬楼的阶数
value[i] 对应着 一次爬楼
(2)过程想法
比较经典,思路也比较好想,但需注意是排列问题
1.4 代码
def up(n,m) -> int:# 物品是每次爬的楼梯数,可重复---->完全背包# 背包容量 n,物品 1~m# 数组:爬到 i 阶,有 dp[i] 种方法dp = [0] * (n+1)# 递推关系:dp[j] += dp[j-i]# 初始化:求方法数,一般初始化 dp[0] = 1,若是0则后续将全是 0 dp[0] = 1for j in range(1,n+1): # 遍历背包for i in range(1,m+1): # 遍历物体if j >= i:dp[j] += dp[j-i]return dp[n]if __name__ == "__main__":# 从键盘端一次性连续读取两个数字inputs = input()# 将输入拆分为两个数字num1, num2 = map(int, inputs.split())print(up(num1,num2))
二、零钱兑换
2.1 题目
给你一个整数数组 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] <= 2^31 - 10 <= amount <= 10^4
2.2 题目链接
322.零钱兑换
2.3 解题思路与过程想法
(1)解题思路
# 数组:构成总金额 j 所需的最少硬币数 dp[j]
# 初始化:初始一个不会覆盖其他值的原始值(求最小,赋无穷大)
# 递推关系:dp[j] = min(dp[j],dp[j-coin]+1)
# 完全背包的组合问题:先遍历物体,后遍历背包容量
(2)过程想法
针对纯完全背包问题变化不是很大,代码比较好写
2.4 代码
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 完全背包:组合问题# 数组:构成总金额 j 所需的最少硬币数 dp[j]# 初始化:初始一个不会覆盖其他值的原始值dp = [float('inf')] * (amount+1)# 递推关系:dp[j] = min(dp[j],dp[j-coin]+1)# 初始化 dp[0] = 0# 举例递推 for coin in coins: # 遍历物品for j in range(coin,amount+1): # 遍历背包dp[j] = min(dp[j],dp[j-coin]+1)return dp[amount] if dp[amount] != float('inf') else -1
三、完全平方数
3.1 题目
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
示例 2:
输入:n = 13 输出:2 解释:13 = 4 + 9
提示:
1 <= n <= 10^4
3.2 题目链接
279.完全平方数
3.3 解题思路与过程想法
(1)解题思路
分析:整个题目的变体主要在于“完全平方数”,为了便于遍历,以其需“平方”的数为遍历数。
# 数组:i 最少可由 dp[i] 个完全平方数组成
# 初始化:初始一个不会覆盖其他值的原始值(求最小,赋无穷大)
# 递推关系:dp[j] = min(dp[j],dp[j-i*i]+1)
# 完全背包的组合问题:先遍历物体,后遍历背包容量
(2)过程想法
分析出变化的关系,代码是很好写的
3.4 代码
class Solution:def numSquares(self, n: int) -> int:# 完全背包问题-组合问题# 数组:i 最少可由 dp[i] 个完全平方数组成dp = [float('inf')] * (n+1)# 递推关系:dp[j] = min(dp[j],dp[j-i*i]+1)# 初始化dp[0] = 0for i in range(n//2+1): # 遍历物体for j in range(i*i,n+1): # 遍历背包dp[j] = min(dp[j], dp[j - i*i]+1)# 处理边界情况return dp[n] if n != 1 else 1相关文章:
研习代码 day39 | 动态规划——完全背包的应用
一、爬楼梯(进阶版) 1.1 题目 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 < m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述 输入共一…...
Rust语言入门教程(五) - 流控制语句
if 表达式 在Rust中, if语句的判断条件不需要用( )括起来, 它会认为所有在if 和 {之间的表达式就是判断条件,例如: if num 5 {msg "five"; }判断条件的表达式必须返回一个bool型的值, 因为Rust是一个不喜…...
字符串:leetcode1410. HTML 实体解析器
1410. HTML 实体解析器 「HTML 实体解析器」 是一种特殊的解析器,它将 HTML 代码作为输入,并用字符本身替换掉所有这些特殊的字符实体。 HTML 里这些特殊字符和它们对应的字符实体包括: 双引号:字符实体为 " ÿ…...
springboot+vue项目如何集成onlyoffice开源文档组件
一、onlyoffice是什么 ONLYOFFICE 是一个开源的办公套件,适合多人在线协作。由总部位于总部在拉脱维亚的 IT 公司Acensio System SIA 开发。它提供在线协作文档编辑器(包括文档、电子表格、演示文稿和表单),适用于 Windows、Linu…...
Android okhttp3.0配置https信任所有证书
参考: Android okhttp3.0配置https的自签证书和信任所有证书 private OkHttpClient getHttpsClient() {OkHttpClient.Builder okhttpClient new OkHttpClient().newBuilder();//信任所有服务器地址okhttpClient.hostnameVerifier(new HostnameVerifier() {Overridepublic boo…...
大数据基础设施搭建 - Hive
文章目录 一、上传压缩包二、解压压缩包三、配置环境变量四、初始化元数据库4.1 配置MySQL地址4.2 拷贝MySQL驱动4.3 初始化元数据库4.3.1 创建数据库4.3.2 初始化元数据库 五、启动元数据服务metastore5.1 修改配置文件5.2 启动/关闭metastore服务 六、启动hiveserver2服务6.1…...
手把手教你安装 Visual Studio 2022 及其简单使用
软件下载 打开 Visual Studio 官网,个人选择免费的Community社区版就够用了。 软件安装 双击运行安装程序: 点击继续 即可: 等待加载完成: 可以看到 Visual Studio 2022 对应不同的开发需求提供了若干工作负载,这里以…...
在MySQL中,修改字段A相同的记录的字段B ,要使得字段C小的记录的字段B值等于字段C大的记录的字段B值
例如:更新具有相同电话号码的用户记录,使得updatetime小的记录的name值等于updatetime大的记录的name值。 首先,我们需要创建一个用户表,这个用户表包含以下字段:phone,updatetime, name。以下是创建这个表…...
Java WebSocket 客户端接收大量数据
介绍 WebSocket 是一种基于 TCP 协议的全双工通信协议,它能够在客户端和服务器之间建立一个持久连接,实现实时的双向数据传输。在实际应用中,有时候我们需要处理大量的数据,例如实时监控系统或者实时股票行情等。本文将介绍如何使…...
QT 在Windows下实现ping功能(ICMP)
前言 很多时候,我们可能会图省事直接调用系统中的ping命令,但这是很不科学的~ 废话不多说,直接上代码.. .pro文件 在.pro文件末尾添加一行: LIBS -liphlpapi -lws2_32 .h文件 在.h文件中加入: #include <Q…...
harmonyos应用开发者高级认证考试部分答案
1只要使用端云一体化的云端资源就需要支付费用(错) 2所有使用Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期函数。(错) 3 HarmonyOS应用可以兼容OpenHarmony生态(对&#…...
基于 STM32Cube.AI 的嵌入式人脸识别算法实现
本文介绍了如何使用 STM32Cube.AI 工具开发嵌入式人脸识别算法。首先,我们将简要介绍 STM32Cube.AI 工具和 STM32F系列单片机的特点。接下来,我们将详细讨论如何使用 STM32Cube.AI 工具链和相关库来进行人脸识别算法的开发和优化。最后,我们提…...
ElasticSearch之cat allocation API
查看各节点上各个shard的硬件使用情况,命令样例如下: curl -X GET "https://localhost:9200/_cat/allocation?vtrue&pretty" --cacert $ES_HOME/config/certs/http_ca.crt -u "elastic:ohCxPHQBEs5*lo7F9"执行结果如下&#x…...
Vue + Element UI 实现复制当前行数据功能(复制到新增页面组件值不能更新等问题解决)
1、需求 使用Vue Element UI 实现在列表的操作栏新增一个复制按钮,复制当前行的数据可以打开新增弹窗后亦可以跳转到新增页面,本文实现为跳转到新增页面。 2、实现 1)列表页 index.vue <el-table> <!-- 其他列 --> <el-t…...
嵌入式FPGA IP正在发现更广阔的用武之地
作者:郭道正, Achronix Semiconductor中国区总经理 在日前落幕的“中国集成电路设计业2023年会暨广州集成电路产业创新发展高峰论坛(ICCAD 2023)”上,Achronix的Speedcore™嵌入式FPGA硅知识产权(eFPGA IP)…...
[点云分割] 条件欧氏聚类分割
介绍 条件欧氏聚类分割是一种基于欧氏距离和条件限制的点云分割方法。它通过计算点云中点与点之间的欧氏距离,并结合一定的条件限制来将点云分割成不同的区域或聚类。 在条件欧氏聚类分割中,通常会定义以下两个条件来判断两个点是否属于同一个聚类&…...
Spring事务粒度优化与传播机制
在Spring事务中,我们通常会为了控制事务粒度,会把它进行拆分,为了避免大事务执行太久,占用资源太多,导致资源利用率低的问题。 我们曾经就遇到老系统因为大事务,把服务打死了。 问题出在一个大事务中有一…...
MySQL 基于成本的优化
其实在MySQL中⼀条查询语句的执⾏成本是由下边这两个⽅⾯组成的: I/O成本 我们的表经常使⽤的MyISAM、InnoDB存储引擎都是将数据和索引都存储到磁盘上的,当我们想查询表中的记录时,需要先把数据或者索引加载到内存中 然后再操作。这个从磁盘…...
【maven】【IDEA】idea中使用maven编译项目,报错java: 错误: 找不到符号 【2】
idea中使用maven编译项目,报错java: 错误: 找不到符号 错误状况展示: 如果报这种错,是因为项目中真的找不到报错的方法或者枚举 字段之类的,但实际是 : 点击 File Path...
AIGC,ChatGPT AI绘画 Midjourney 注册流程详细步骤
AI 绘画,Midjourney完成高清图片绘制,轻松掌握AI工具。 前期准备: ① 一个能使用的谷歌账号 ② 可以访问外网 Midjourney注册 1.进入midjourney官网https://www.midjourney.com 点击左下角”Join the Beta”,就可以注册,第一次使用的小伙伴会弹出提示,只需要点击Acc…...
完全掌握Windows Cleaner:高效使用开源工具解决C盘空间危机
完全掌握Windows Cleaner:高效使用开源工具解决C盘空间危机 【免费下载链接】WindowsCleaner Windows Cleaner——专治C盘爆红及各种不服! 项目地址: https://gitcode.com/gh_mirrors/wi/WindowsCleaner Windows Cleaner是一款专为Windows系统设计…...
老年健身应用开发:自动追踪与适老化设计实践
1. 老年健身应用的设计挑战与机遇随着全球老龄化进程加速,65岁以上人口比例持续攀升,针对老年群体的健康科技产品迎来了前所未有的发展机遇。我在参与Senior Fit项目开发过程中深刻体会到,为老年人设计健身应用绝非简单地将现有产品"放大…...
哔哩下载姬:解锁B站视频离线观看的5个关键技巧
哔哩下载姬:解锁B站视频离线观看的5个关键技巧 【免费下载链接】downkyi 哔哩下载姬downkyi,哔哩哔哩网站视频下载工具,支持批量下载,支持8K、HDR、杜比视界,提供工具箱(音视频提取、去水印等)。…...
Voxtral-4B-TTS-2603实战案例:为老年健康APP定制中性女声慢速播报语音方案
Voxtral-4B-TTS-2603实战案例:为老年健康APP定制中性女声慢速播报语音方案 1. 项目背景与需求分析 随着老龄化社会的到来,老年健康类APP的使用需求日益增长。但在实际应用中,我们发现老年用户群体普遍面临以下语音交互痛点: 语…...
路侧LiDAR背景减除技术:GDG方法与应用
1. 路侧LiDAR背景减除技术概述在智能交通和自动驾驶领域,路侧LiDAR系统正成为基础设施感知层的重要组成部分。这类系统通过部署在路侧杆件上的激光雷达传感器,持续采集周围环境的3D点云数据,为车辆提供超视距感知能力。然而,原始点…...
CMSIS DSP库在Cortex-M55/M85上的性能调优实战:以FFT和卷积为例
CMSIS DSP库在Cortex-M55/M85上的性能调优实战:以FFT和卷积为例 当你在Cortex-M55/M85这样的高性能微控制器上运行数字信号处理算法时,是否遇到过这样的困惑:为什么同样的FFT代码,在不同编译选项下性能差异能达到3倍?为…...
Hunyuan-HY-MT1.5-1.8B实战:REST API封装详细教程
Hunyuan-HY-MT1.5-1.8B实战:REST API封装详细教程 你是不是也遇到过这样的问题:手头有个效果不错的翻译模型,但团队里前端、测试、产品同学都不会写Python,每次调用都要找你跑脚本?或者想把翻译能力集成进现有系统&am…...
别再傻傻分不清了!MATLAB矩阵运算的点乘(.*)和矩阵乘(*)到底啥区别?
MATLAB矩阵运算深度解析:元素级操作与矩阵级操作的本质差异 引言:为什么我们需要区分这两种运算? 在MATLAB的世界里,矩阵运算就像是一把瑞士军刀,功能强大但需要正确使用。许多初学者在使用MATLAB进行科学计算或工程仿…...
BERT命名实体识别实战:从原理到Hugging Face实现
1. 基于BERT的命名实体识别实战指南命名实体识别(NER)是自然语言处理中的一项基础任务,它能从非结构化文本中识别出人名、地名、组织机构名等特定类别的实体。想象一下,当你阅读"微软CEO萨提亚纳德拉在西雅图的会议上发言&qu…...
Qwen3-4B-Thinking部署教程:支持WebSocket长连接的实时流式响应
Qwen3-4B-Thinking部署教程:支持WebSocket长连接的实时流式响应 1. 模型简介 Qwen3-4B-Thinking-2507-Gemini-2.5-Flash-Distill是一个基于vLLM框架部署的文本生成模型,特别优化了WebSocket长连接支持,能够提供实时流式响应体验。该模型在约…...
