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…...
<图像处理> 空间滤波基础
空间滤波基础 图像滤波是一种常见的图像处理技术,用于平滑图像、去除噪音和边缘检测等任务。图像滤波的基本原理是在进行卷积操作时,通过把每个像素的值替换为该像素及其邻域的设定的函数值来修改图像。 预备知识:可分离滤波核、边缘填充。…...
Claude Code 速查表
其中的:键盘快捷键常规控制Ctrl C:取消输入 / 生成Ctrl D:退出会话Ctrl L:清屏Ctrl O:切换详细输出Ctrl R:反向搜索历史Ctrl G:在编辑器中打开提示Ctrl B:后台运行任务Ctrl …...
从游戏报错到完美运行 DirectX修复工具实际应用案例展示
评价一款工具软件的优劣,最具有说服力的方式莫过于通过真实的实际案例来直观展示其效果和价值。 对于系统修复类工具来说,更是如此,因为用户最关心的就是它能否真正解决自己的问题。 DirectX相关问题一直是Windows游戏玩家最常遇到的技术难题…...
家里装了 OpenClaw,在公司也能随时管理——Shield CLI 远程访问方案
家里装了 OpenClaw,在公司也能随时管理 OpenClaw 火到不用介绍了——GitHub 25 万 Star,一个能真正帮你干活的 AI Agent。很多人装在家里的 Windows 电脑上,配好了 API Key 和各种插件,用着很爽。但一到公司或者出门在外ÿ…...
3大核心功能让你轻松掌握League-Toolkit英雄联盟辅助工具
3大核心功能让你轻松掌握League-Toolkit英雄联盟辅助工具 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基…...
HUE Hive编辑器10个隐藏技巧:从拖拽表名到变量查询的高效玩法
HUE Hive编辑器10个隐藏技巧:从拖拽表名到变量查询的高效玩法 1. 拖拽表名生成查询模板的进阶用法 许多HUE用户都知道可以通过拖拽左侧表名到编辑区生成基础查询模板,但很少有人挖掘这个功能的完整潜力。实际上,拖拽操作支持多种智能交互方式…...
ESP32-C3开发环境搭建(VSCode+ESP-IDF)与串口占用疑难排查实战
1. ESP32-C3开发环境搭建全攻略 第一次接触ESP32-C3开发板时,我和大多数开发者一样,被环境搭建这个"入门杀"折腾得够呛。特别是使用合宙经典款开发板时,USB转串口芯片带来的各种"惊喜"让人措手不及。这里分享一套经过实战…...
Element React:革新性UI组件库助力React开发者高效构建企业级应用界面
Element React:革新性UI组件库助力React开发者高效构建企业级应用界面 【免费下载链接】element-react Element UI 项目地址: https://gitcode.com/gh_mirrors/el/element-react 在现代Web应用开发中,界面构建往往占据了开发者大量时间与精力。El…...
如何快速搭建Kafka Docker集群:broker-list.sh工作原理与实用指南
如何快速搭建Kafka Docker集群:broker-list.sh工作原理与实用指南 【免费下载链接】kafka-docker Dockerfile for Apache Kafka 项目地址: https://gitcode.com/gh_mirrors/ka/kafka-docker GitHub 加速计划 / ka / kafka-docker 项目提供了基于 Docker 的 A…...
华为新机散热“封神”:拆解仿生羽翼涡扇,看“小翅膀”如何颠覆手机温控
🎓作者简介:科技自媒体优质创作者 🌐个人主页:莱歌数字-CSDN博客 💌公众号:莱歌数字(B站同名) 📱个人微信:yanshanYH 211、985硕士,从业16年 从…...
10个Twisted Web模块实战技巧:构建高性能HTTP服务器和客户端的终极指南
10个Twisted Web模块实战技巧:构建高性能HTTP服务器和客户端的终极指南 【免费下载链接】twisted Event-driven networking engine written in Python. 项目地址: https://gitcode.com/gh_mirrors/tw/twisted Twisted Web是基于Python的事件驱动网络引擎&…...
