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

动态规划专练( 279.完全平方数)

279.完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,14916 都是完全平方数,而 311 不是。

示例 1:

输入:n = 12
输出:3 
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

提示:

  • 1 <= n <= 104

题解:

本题也是一个完全背包的运用场景。n只能由完全平方数构成,也就是只能由 1 ~ floor(sqrt(n)),这个范围的数的平方。

那么物品就相当于是这1~floor(sqrt(n))个数,物品的重量相当于平方,物品的价值相当于1,背包容量相当于本题的n。求装满背包的最低价值是多少,代码如下:

package com.offer;import com.amazonaws.services.dynamodbv2.xspec.M;/*** 给你一个整数 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 <= 104* @author bwzfy* @create 2024/4/15**/
public class _279完全平方数 {public static void main(String[] args) {System.out.println(numSquares(12));}public static int numSquares(int n) {int max = (int) Math.floor(Math.sqrt(n));// 1 ~ max, 1 ~ nint[] dp = new int[n + 1];for (int i = 1; i < n + 1; i++) {dp[i] = i;}for (int i = 2; i < max + 1; i++) {for (int j = 2; j < n + 1; j++) {if (i * i <= j) {dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}}return dp[n];}
}

相关文章:

动态规划专练( 279.完全平方数)

279.完全平方数 给你一个整数 n &#xff0c;返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数&#xff0c;其值等于另一个整数的平方&#xff1b;换句话说&#xff0c;其值等于一个整数自乘的积。例如&#xff0c;1、4、9 和 16 都是完全平方数&#xff0c;而 …...

京东商品详情API接口(商品属性丨sku价格丨详情图丨标题等数据)

京东商品详情API接口是京东开放平台提供的一种API接口&#xff0c;通过调用该接口&#xff0c;开发者可以获取京东商品的标题、价格、库存、月销量、总销量、详情描述、图片等详细信息。下面针对您提到的商品属性、SKU价格、详情图以及标题等数据&#xff0c;做具体介绍&#x…...

Springboot+Vue项目-基于Java+MySQL的校园周边美食探索及分享平台系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…...

折叠面板组件(vue)

代码 <template><div class"collapse-info"><div class"collapse-title"><div class"title-left">{{ title }}</div><div click"changeHide"> <Button size"small" v-if"sho…...

【Canvas技法】蓝底金字北岛诗节选(径向渐变色、文字阴影示例)

【效果图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>北岛诗选</title><style type"text/css">.c…...

【大语言模型】基础:TF-IDF

TF-IDF (Term Frequency-Inverse Document Frequency) 是一种用于信息检索与文本挖掘的统计方法&#xff0c;用来评估一个词对于一个文件集或一个语料库中的其中一份文件的重要性。它是一种常用于文本处理和自然语言处理的权重计算技术。 原理 TF-IDF 由两部分组成&#xff1…...

[开发日志系列]PDF图书在线系统20240415

20240414 Step1: 创建基础vueelment项目框架[耗时: 1h25min(8:45-10:10)] 检查node > 升级至最新 (考虑到时间问题,没有使用npm命令行执行,而是觉得删除重新下载最新版本) > > 配置vue3框架 ​ 取名:Online PDF Book System 遇到的报错: 第一报错: npm ERR! …...

蓝桥杯 — — 纯质数

纯质数 题目&#xff1a; 思路&#xff1a; 一个最简单的思路就是枚举出所有的质数&#xff0c;然后再判断这个质数是否是一个纯质数。 枚举出所有的质数&#xff1a; 可以使用常规的暴力求解法&#xff0c;其时间复杂度为&#xff08; O ( N N ) O(N\sqrt{N}) O(NN ​)&…...

OpenCV基本图像处理操作(三)——图像轮廓

轮廓 cv2.findContours(img,mode,method) mode:轮廓检索模式 RETR_EXTERNAL &#xff1a;只检索最外面的轮廓&#xff1b;RETR_LIST&#xff1a;检索所有的轮廓&#xff0c;并将其保存到一条链表当中&#xff1b;RETR_CCOMP&#xff1a;检索所有的轮廓&#xff0c;并将他们组…...

比特币突然暴跌

作者&#xff1a;秦晋 周末愉快。 今天给大家分享两则比特币新闻&#xff0c;也是两个数据。一则是因为中东地缘政治升温&#xff0c;传统资本市场的风险情绪蔓延至加密市场&#xff0c;引发加密市场暴跌。比特币跌至66000美元下方。杠杆清算金额高达8.5亿美元。 二则是&#x…...

使用SpeechRecognition和vosk处理ASR

SpeechRecognition可以支持多种模型语音转文字&#xff0c;感觉vosk还不错&#xff0c;使用起来也简单一些&#xff1b;百度也有PaddleSpeech&#xff0c;但是安装起来太麻烦&#xff0c;不是这个库版本不对就是那个库有问题&#xff0c;用起来不方便&#xff1b; 安装SpeechR…...

【Go】通道:缓冲通道和非缓冲通道

目录 通道的基本概念 缓冲通道 非缓冲通道 总结 通道的基本概念 在Go语言中&#xff0c;通道是一种特殊的类型&#xff0c;用于在goroutine之间传递数据。你可以将通道想象为数据的传输管道。通道分为两种类型&#xff1a; 非缓冲通道&#xff08;Unbuffered Channels&…...

Java中数组的使用

在Java编程中&#xff0c;数组是一种非常重要的数据结构&#xff0c;它允许我们存储相同类型的多个元素。对于初学者来说&#xff0c;理解数组的基本概念、初始化、遍历、默认值以及内存分配和使用注意事项是非常关键的。 一、数组的概念 数组是一个可以容纳多个相同类型数据…...

CAP5_Monday

A Set to Max (Easy Version) 给定数组 a 和 b&#xff0c;可以执行以下操作任意次 : 让 a l ∼ a r a_l\sim a_r al​∼ar​ 中的所有所有元素变成 a i a_i ai​ ( l ≤ i ≤ r ) (l\leq i\leq r) (l≤i≤r)&#xff0c; 其中 1 ≤ l ≤ r ≤ n 1\leq l \leq r \leq n 1≤…...

科大讯飞星火开源大模型iFlytekSpark-13B GPU版部署方法

星火大模型的主页&#xff1a;iFlytekSpark-13B: 讯飞星火开源-13B&#xff08;iFlytekSpark-13B&#xff09;拥有130亿参数&#xff0c;新一代认知大模型&#xff0c;一经发布&#xff0c;众多科研院所和高校便期待科大讯飞能够开源。 为了让大家使用的更加方便&#xff0c;科…...

SpringBoot基于RabbitMQ实现消息延迟队列方案

知识小科普 在此之前&#xff0c;简单说明下基于RabbitMQ实现延时队列的相关知识及说明下延时队列的使用场景。 延时队列使用场景 在很多的业务场景中&#xff0c;延时队列可以实现很多功能&#xff0c;此类业务中&#xff0c;一般上是非实时的&#xff0c;需要延迟处理的&a…...

Go语言使用标准库时常见错误

Go的标准库是一组增加和拓展语言的核心包。然而,很容易误用标准库,或者我们对其行为理解有限,导致产生了bug或不应该在生产级应用程序中某些功能。 1. 提供错误的持续时间 标准库提供了获取 time.Duration 的常用函数和方法,但由于 time.Duration 是 int64 的自定义类型,…...

UE5不打包启用像素流 ubuntu22.04

首先查找引擎中像素流的位置&#xff1a; zkzk-ubuntu2023:/media/zk/Data/Linux_Unreal_Engine_5.3.2$ sudo find ./ -name get_ps_servers.sh [sudo] zk 的密码&#xff1a; ./Engine/Plugins/Media/PixelStreaming/Resources/WebServers/get_ps_servers.sh然后在指定路径中…...

Redis 常用数据类型常用命令和应用场景

首先先混个眼熟 Redis 中的 8 种常用数据类型&#xff1a; 5 种基础数据类型&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;集合&#xff09;、Hash&#xff08;散列&#xff09;、Zset&#xff08;有序集合&#xff0…...

ins视频批量下载,instagram批量爬取视频信息

简介 Instagram 是目前最热门的社交媒体平台之一,拥有大量优质的视频内容。但是要逐一下载这些视频往往非常耗时。在这篇文章中,我们将介绍如何使用 Python 编写一个脚本,来实现 Instagram 视频的批量下载和信息爬取。 我们使用selenium获取目标用户的 HTML 源代码,并将其保存…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

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": …...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...