70. 爬楼梯 (进阶),322. 零钱兑换,279.完全平方数
代码随想录训练营第45天|70. 爬楼梯 (进阶,322. 零钱兑换,279.完全平方数
- 70.爬楼梯
- 文章
- 思路
- 代码
- 322.零钱兑换
- 文章
- 思路
- 代码
- 279.完全平方数
- 文章
- 思路
- 代码
- 总结
70.爬楼梯
文章
代码随想录|0070.爬楼梯完全背包版本
思路
将楼梯长度视为背包容量,将一步的跨度视为物品价值,则可以转化为完全背包问题
代码
class Solution {public int climbStairs(int n) {int i, j;int[] dp = new int[n + 1];dp[0] = 1;for (j = 0; j < n + 1; ++j) {for (i = 0; i < 2; ++i) {if (j >= i + 1) {dp[j] += dp[j - i - 1];}}}return dp[n];}
}
322.零钱兑换
文章
代码随想录|0322.零钱兑换
思路
dp数组初始化全为正无穷
dp[0]单独设为0
外层遍历物品,内层遍历背包容积
d p [ j ] = M i n ( d p [ j ] , d p [ j − c o i n s [ i ] ] + 1 ) dp[j]=Min(dp[j], dp[j-coins[i]]+1) dp[j]=Min(dp[j],dp[j−coins[i]]+1)
代码
public class Solution {public int coinChange(int[] coins, int amount) {int max = amount + 1;int[] dp = new int[amount + 1];Arrays.fill(dp, max);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int j = 0; j < coins.length; j++) {if (coins[j] <= i) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
}
279.完全平方数
文章
代码随想录|0279.完全平方数
思路
n为背包容量,i^2为物品价值,单个物品最大价值为sqrt(n)
d p [ j ] = M i n ( d p [ j ] , d p [ j − i 2 ] + 1 ) dp[j]=Min(dp[j],dp[j-i^2]+1) dp[j]=Min(dp[j],dp[j−i2]+1)
代码
class Solution {public int numSquares(int n) {int i, j;int[] dp = new int[n + 1];Arrays.fill(dp, n);dp[0] = 0;int upper = (int) Math.sqrt(n);for (i = 1; i <= upper; ++i) {for (j = 1; j < n + 1; ++j) {if (j >= i * i) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}return dp[n];}
}
总结
二刷,还是会出错
牢牢记住,求组合数外层物品内层背包
相关文章:
70. 爬楼梯 (进阶),322. 零钱兑换,279.完全平方数
代码随想录训练营第45天|70. 爬楼梯 (进阶,322. 零钱兑换,279.完全平方数 70.爬楼梯文章思路代码 322.零钱兑换文章思路代码 279.完全平方数文章思路代码 总结 70.爬楼梯 文章 代码随想录|0070.爬楼梯完全背包版本 思路 将楼梯长度视为背…...
Apache Doris 2.0 如何实现导入性能提升 2-8 倍
数据导入吞吐是 OLAP 系统性能的重要衡量标准之一,高效的数据导入能力能够加速数据实时处理和分析的效率。随着 Apache Doris 用户规模的不断扩大, 越来越多用户对数据导入提出更高的要求,这也为 Apache Doris 的数据导入能力带来了更大的挑战…...
RabbitMQ: topic 结构
生产者 package com.qf.mq2302.topic;import com.qf.mq2302.utils.MQUtils; import com.rabbitmq.client.Channel; import com.rabbitmq.client.Connection;public class Pubisher {public static final String EXCHANGE_NAME"mypubilisher";public static void ma…...
信息系统项目管理教程(第4版):第二章 信息技术及其发展
请点击↑关注、收藏,本博客免费为你获取精彩知识分享!有惊喜哟!! 第二章 信息技术及其发展 2.1信息技术及其发展 信息技术是以微电子学为基础的计算机技术和电信技术的结合而形成的,对声音的、图像的、文字的、数字…...
有哪些适合初学者的编程语言?
C语言 那为什么我还要教你C语言呢?因为我想要让你成为一个更好、更强大的程序员。如果你要变得更好,C语言是一个极佳的选择,其原因有二。首先,C语言缺乏任何现代的安全功能,这意味着你必须更为警惕,时刻了…...
uni-app动态tabBar,根据不同用户展示不同的tabBar
1.uni框架的api实现 因为我们用的是uni-app框架开发,所以在创建项目的时候直接创建uni-ui的项目即可,这个项目模板中自带了uni的一些好用的组件和api。 起初我想着这个效果不难实现,因为官方也有api可以直接使用,所以我最开始尝试…...
手写Spring:第6章-资源加载器解析文件注册对象
文章目录 一、目标:资源加载器解析文件注册对象二、设计:资源加载器解析文件注册对象三、实现:资源加载器解析文件注册对象3.1 工程结构3.2 资源加载器解析文件注册对象类图3.3 类工具类3.4 资源加载接口定义和实现3.4.1 定义资源加载接口3.4…...
Redis 7 第八讲 集群模式(cluster)架构篇
集群架构 Redis 集群架构图 集群定义 Redis 集群是一个提供在多个Redis节点间共享数据的程序集;Redis集群可以支持多个master 应用场景 Redis集群支持多个master,每个master又可以挂载多个slave读写分离支持数据的高可用支持海量数据的读写存储操作集群自带Sentinel的故障…...
【PowerQuery】导入与加载XML
在标准数据格式类型里面,有一类比较特殊的数据类型,就是层次结构数据。层次结构数据和标准的结构型数据方式完全不同,在实际应用过程中使用最为频繁的几种数据类型如下。 XML数据格式Json 数据格式Yaml 数据格式我们将在本节和大家一起分享下XML格式数据集成,下一节和大家分…...
vue 预览视频
1.预览本地文件 1.1 直接给video或者embed的src赋值本地路径 <video :src"videoUrl"></video> // 或者 使用embed标签<embed :src"videoUrl" /> 1.2 读取文件流形式 <input type"file" ref"file" /> <vi…...
4个维度讲透ChatGPT技术原理,揭开ChatGPT神秘技术黑盒!(文末送书)
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
【无标题】@Scheduled 的cron
, :指定多个值。 -:表示一个区间。 / :指定一个值的增加幅度。n/m表示从n开始,每次增加m。 L:是last的缩写,表示最后一天,用在日表示一个月中的最后一天,用在周表示每周最后一天&…...
IP和MAC的作用区别
在 IP 地址的上一行是 link/ether fa:16:3e:c7:79:75 brd ff:ff:ff:ff:ff:ff,这个被称为 MAC 地址,是一个网卡的物理地址,用十六进制,6 个 byte 表示。 一个网络包要从一个地方传到另一个地方,除了要有确定的地址&…...
python趣味编程-数独游戏
数独游戏是一个用Python编程语言编写的应用程序。该项目包含可以显示实际应用程序的基本功能。该项目可以让修读 IT 相关课程并希望开发简单应用程序的学生受益。这个Python 数独游戏是一个简单的项目,可用于学习tkinter库的实践。这个数独游戏可以提供Python编程的基本编码技…...
MySQL/MariaDB 查询某个 / 多个字段重复数据
创建测试表和数据 # 创建表 create table if not exists t_duplicate (name varchar(255) not null,age int not null );# 插入测试数据 insert into t_duplicate(name, age) values(a, 1); insert into t_duplicate(name, age) values(a, 2);查询单个字段重复 使用 count() …...
【力扣每日一题】2023.9.10 课程表Ⅱ
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 今天的题目和昨天类似,不过今天要我们求出学习所有课程的先后顺序。 昨天只需要我们求出能否学习完所有课程,因此…...
VSCODE CMAKE C++ 工程调试, C++不以科学计数法输出并控制小数位数
1. VSCODE调试CMAKE工程配置1.1 修改CMakeLists.txt文件1.2. 程序中1.3. launch.json配置1.4 开始调试1.5 注意 2. C设置输出浮点数且保留位数固定 1. VSCODE调试CMAKE工程配置 1.1 修改CMakeLists.txt文件 加这一句 set(CMAKE_BUILD_TYPE "Debug")1.2. 程序中 在…...
Drools规则引擎入门学习记录
业务开发过程中,对于某些判断性的通用规则是基于if-else封装,还是基于策略模式封装?无论以上那种封装出来的方法,只能在单体软件包中共用,且不能无感部署,然而对于业务而言,可能规则改变的比较频…...
肖sir__设计测试用例方法之判定表06_(黑盒测试)
设计测试用例方法之判定表 1、判定表:是一种表达逻辑判断的工具。 2、判定表:包含四部分 1)条件桩(condition stub):列出问题的 所有条件(通常条件次序无关紧要)。 2)条件项&#x…...
<图像处理> 空间滤波基础
空间滤波基础 图像滤波是一种常见的图像处理技术,用于平滑图像、去除噪音和边缘检测等任务。图像滤波的基本原理是在进行卷积操作时,通过把每个像素的值替换为该像素及其邻域的设定的函数值来修改图像。 预备知识:可分离滤波核、边缘填充。…...
用MobaXterm替代传统终端的完整指南
Windows远程运维革命:用MobaXterm替代传统终端的完整指南 每次打开 PuTTY 时,你是否会对着那个灰暗的界面叹气?当需要在Xshell中频繁切换标签时,是否感到效率低下?作为Windows系统管理员或开发者,我们长期忍…...
Venera:5大革新功能打造无缝全平台漫画阅读体验
Venera:5大革新功能打造无缝全平台漫画阅读体验 【免费下载链接】venera A comic app 项目地址: https://gitcode.com/gh_mirrors/ve/venera Venera 是一款开源跨平台漫画应用,专为漫画爱好者打造全设备同步的阅读解决方案。无论你使用 Windows、…...
追踪Elsevier审稿进度:开源工具如何提升学术投稿效率
追踪Elsevier审稿进度:开源工具如何提升学术投稿效率 【免费下载链接】Elsevier-Tracker 项目地址: https://gitcode.com/gh_mirrors/el/Elsevier-Tracker 学术出版流程中,审稿进度的不确定性常给研究者带来困扰。Elsevier作为全球领先的学术出版…...
英雄联盟智能助手如何解决游戏操作繁琐问题?提升游戏效率完全指南
英雄联盟智能助手如何解决游戏操作繁琐问题?提升游戏效率完全指南 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是…...
基于COMSOL 5.5的精确非局部损伤模型:模拟脆性材料压缩、摩擦和剪切条件下的破坏行为研究
开发了一种基于COMSOL 5.5的损伤模型,专门用于模拟脆性材料在压缩、摩擦和剪切条件下的破坏行为。 该模型采用非局部本构关系,通过考虑材料内部微观结构的影响,精确捕捉脆性材料在受力过程中的应力分布和破坏机理。脆性材料的破坏模拟一直是工…...
Llama-3.2V-11B-cot部署详解:自动修复视觉权重加载致命Bug全过程
Llama-3.2V-11B-cot部署详解:自动修复视觉权重加载致命Bug全过程 1. 项目概述 Llama-3.2V-11B-cot是基于Meta Llama-3.2V-11B-cot多模态大模型开发的高性能视觉推理工具,专为双卡RTX 4090环境深度优化。本工具通过自动修复视觉权重加载等核心Bug&#…...
从‘生日悖论’到‘碰撞攻击’:一个故事讲明白哈希函数为什么会被攻破
从生日派对到数字指纹:哈希函数的安全冒险之旅 想象一下,你正在参加一个23人的小型生日派对。服务员突然打赌说:"这里至少有两个人同一天生日。"你环顾四周觉得概率渺茫——毕竟一年有365天呢。但惊人的是,这个赌注的胜…...
3种方法永久保存QQ空间历史说说:GetQzonehistory实战指南
3种方法永久保存QQ空间历史说说:GetQzonehistory实战指南 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 为什么需要GetQzonehistory:三个真实场景 想象一下&am…...
2026电商客服外包TOP5实力品牌详细解读
进入2026年,电商行业已从粗放式扩张转向精细化运营时代,客户服务不再局限于简单的问答回复,而是成为驱动店铺销售增长、积累品牌声誉的关键要素。根据最新行业研究报告,专业的外包客服团队能够帮助店铺将询单转化率提高20%-30%&am…...
3分钟完成Axure RP中文界面汉化:终极完整指南
3分钟完成Axure RP中文界面汉化:终极完整指南 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包,不定期更新。支持 Axure 9、Axure 10。 项目地址: https://gitcode.com/gh_mirrors/ax/axure-cn 还在为Axu…...
