当前位置: 首页 > news >正文

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[jcoins[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[ji2]+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. 爬楼梯 &#xff08;进阶&#xff0c;322. 零钱兑换&#xff0c;279.完全平方数 70.爬楼梯文章思路代码 322.零钱兑换文章思路代码 279.完全平方数文章思路代码 总结 70.爬楼梯 文章 代码随想录|0070.爬楼梯完全背包版本 思路 将楼梯长度视为背…...

Apache Doris 2.0 如何实现导入性能提升 2-8 倍

数据导入吞吐是 OLAP 系统性能的重要衡量标准之一&#xff0c;高效的数据导入能力能够加速数据实时处理和分析的效率。随着 Apache Doris 用户规模的不断扩大&#xff0c; 越来越多用户对数据导入提出更高的要求&#xff0c;这也为 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版):第二章 信息技术及其发展

请点击↑关注、收藏&#xff0c;本博客免费为你获取精彩知识分享&#xff01;有惊喜哟&#xff01;&#xff01; 第二章 信息技术及其发展 2.1信息技术及其发展 信息技术是以微电子学为基础的计算机技术和电信技术的结合而形成的&#xff0c;对声音的、图像的、文字的、数字…...

有哪些适合初学者的编程语言?

C语言 那为什么我还要教你C语言呢&#xff1f;因为我想要让你成为一个更好、更强大的程序员。如果你要变得更好&#xff0c;C语言是一个极佳的选择&#xff0c;其原因有二。首先&#xff0c;C语言缺乏任何现代的安全功能&#xff0c;这意味着你必须更为警惕&#xff0c;时刻了…...

uni-app动态tabBar,根据不同用户展示不同的tabBar

1.uni框架的api实现 因为我们用的是uni-app框架开发&#xff0c;所以在创建项目的时候直接创建uni-ui的项目即可&#xff0c;这个项目模板中自带了uni的一些好用的组件和api。 起初我想着这个效果不难实现&#xff0c;因为官方也有api可以直接使用&#xff0c;所以我最开始尝试…...

手写Spring:第6章-资源加载器解析文件注册对象

文章目录 一、目标&#xff1a;资源加载器解析文件注册对象二、设计&#xff1a;资源加载器解析文件注册对象三、实现&#xff1a;资源加载器解析文件注册对象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神秘技术黑盒!(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

【无标题】@Scheduled 的cron

, &#xff1a;指定多个值。 -&#xff1a;表示一个区间。 / &#xff1a;指定一个值的增加幅度。n/m表示从n开始&#xff0c;每次增加m。 L&#xff1a;是last的缩写&#xff0c;表示最后一天&#xff0c;用在日表示一个月中的最后一天&#xff0c;用在周表示每周最后一天&…...

IP和MAC的作用区别

在 IP 地址的上一行是 link/ether fa:16:3e:c7:79:75 brd ff:ff:ff:ff:ff:ff&#xff0c;这个被称为 MAC 地址&#xff0c;是一个网卡的物理地址&#xff0c;用十六进制&#xff0c;6 个 byte 表示。 一个网络包要从一个地方传到另一个地方&#xff0c;除了要有确定的地址&…...

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 课程表Ⅱ

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 今天的题目和昨天类似&#xff0c;不过今天要我们求出学习所有课程的先后顺序。 昨天只需要我们求出能否学习完所有课程&#xff0c;因此…...

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规则引擎入门学习记录

业务开发过程中&#xff0c;对于某些判断性的通用规则是基于if-else封装&#xff0c;还是基于策略模式封装&#xff1f;无论以上那种封装出来的方法&#xff0c;只能在单体软件包中共用&#xff0c;且不能无感部署&#xff0c;然而对于业务而言&#xff0c;可能规则改变的比较频…...

肖sir__设计测试用例方法之判定表06_(黑盒测试)

设计测试用例方法之判定表 1、判定表&#xff1a;是一种表达逻辑判断的工具。 2、判定表&#xff1a;包含四部分 1&#xff09;条件桩&#xff08;condition stub&#xff09;:列出问题的 所有条件&#xff08;通常条件次序无关紧要&#xff09;。 2&#xff09;条件项&#x…...

<图像处理> 空间滤波基础

空间滤波基础 图像滤波是一种常见的图像处理技术&#xff0c;用于平滑图像、去除噪音和边缘检测等任务。图像滤波的基本原理是在进行卷积操作时&#xff0c;通过把每个像素的值替换为该像素及其邻域的设定的函数值来修改图像。 预备知识&#xff1a;可分离滤波核、边缘填充。…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...