力扣 -- 279. 完全平方数(完全背包问题)

解题步骤:





参考代码:
未优化代码:
class Solution {
public:int numSquares(int n) {const int INF=0x3f3f3f3f;int m=sqrt(n);//多开一行,多开一列vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化第一行dp[0][0]=0;for(int j=1;j<=n;j++){dp[0][j]=INF;}//第一列不需要初始化//填表for(int i=1;i<=m;i++){//记得从0开始,因为第一列没有初始化for(int j=0;j<=n;j++){//状态转移方程dp[i][j]=dp[i-1][j];if(j>=i*i){dp[i][j]=min(dp[i][j],dp[i][j-i*i]+1);}}}//返回值,m就是根号nreturn dp[m][n];}
};
优化后的代码:
class Solution {
public:int numSquares(int n) {const int INF=0x3f3f3f3f;int m=sqrt(n);//多开一行,多开一列,初始化vector<int> dp(n+1,INF);dp[0]=0;//填表for(int i=1;i<=m;i++){//记得从0开始,因为第一列没有初始化for(int j=i*i;j<=n;j++){//状态转移方程dp[j]=min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};
你学会了吗???
相关文章:
力扣 -- 279. 完全平方数(完全背包问题)
解题步骤: 参考代码: 未优化代码: class Solution { public:int numSquares(int n) {const int INF0x3f3f3f3f;int msqrt(n);//多开一行,多开一列vector<vector<int>> dp(m1,vector<int>(n1));//初始化第一行…...
在将对象 => JSON格式时,无法序列化部分属性
问题现象: 在ssm项目中,一个controller返回Msg对象(自定义对象,包含三个属性,int code;String msg;HashMap map;同时这三个属性都有对应的get和set方法),我的map属性里面…...
用python表格初级尝试
Excel,我的野心 当我输入3,2 就表示在第3行第2列。的单元格输入数据input输入表头 (input内除了/,空格 回车 标点符号等 全部作为单元格分隔符)由我设置input输入的是行or列 给选项 1. 行 2. 列默认回车或没输入值是列由我设置起…...
【单片机】16-LCD1602和12864显示器
1.LCD显示器相关背景 1.LCD简介 (1)显示器,常见显示器:电视,电脑 (2)LCD(Liquid Crystal Display),液晶显示器,原理介绍 (3ÿ…...
AUTOSAR从入门到精通-基于 CAN 总线的汽车发电机智能调节器(下)
目录 4.4.3 CAN 通信软件实现 汽车发电机智能调节器试验与结果分析 5.1 试验方案设计...
Windows下Tensorflow docker python开发环境搭建
前置条件 windows10 更新到较新的版本,硬件支持Hyper-V。 参考:https://learn.microsoft.com/zh-cn/windows/wsl/install 启用WSL 在Powershell中输入如下指令: dism.exe /online /enable-feature /featurename:Microsoft-Windows-Subsys…...
idea常用快捷键 idea搜索快捷键
常用快捷键 IntelliJ IDEA 是一款流行的 Java 集成开发环境(IDE),有许多常用的快捷键可以帮助开发者提高效率。以下是一些常用的 IntelliJ IDEA 快捷键: CtrlSpace:基本代码补全,用于输入任何东西&#x…...
Redis Cluster Gossip Protocol: MEET
返回目录 CLUSTER MEET 过程说明 #mermaid-svg-dp95n6LRjBO1mCKE {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-dp95n6LRjBO1mCKE .error-icon{fill:#552222;}#mermaid-svg-dp95n6LRjBO1mCKE .error-text{fill:#…...
TcpConnection的读写操作【深度剖析】
文章目录 前言一、TcpConnection的读二、TcpConnection的写三、TcpConnection的关闭 前言 今天总结TcpConnection类的读写事件。 一、TcpConnection的读 当Poller检测到套接字的Channel处于可读状态时,会调用Channel的回调函数,回调函数中根据不同激活…...
k8s面试题
1 简述etcd及其特点 ETCD是高可用分布式的键值存储系统 特点 1)强一致性:即使部分节点故障,etcd仍能正常工作,并保持数据一致 (强一致性:分布式系统中,更新操作,所有节点读取的数据都是最新的,一致的) 2)高可用:etcd支持数据多副本复制,一个节点挂,其他节点接…...
OpenCV 4.x 版本的新特性都有哪些?
文章大纲 V 4. 0DNNV 4.0 - 4. 8cheatsheetvideo analysis参考文献与学习路径2016年的时候我快研究生毕业了,那时候OpenCV 2.4.x 版本非常的流行,当时3.x 的版本刚发布,很多人都没有用习惯。 我写过一遍笔记: OpenCV 3.0 3.1版本的改进家里还有一本书:《OpenCV 3 计算机视…...
Redisson—分布式集合
7.1. 映射(Map) 基于Redis的Redisson的分布式映射结构的RMap Java对象实现了java.util.concurrent.ConcurrentMap接口和java.util.Map接口。与HashMap不同的是,RMap保持了元素的插入顺序。该对象的最大容量受Redis限制,最大元素数…...
93、Redis 之 使用连接池管理Redis6.0以上的连接 及 消息的订阅与发布
★ 使用连接池管理Redis连接 从Redis 6.0开始,Redis可支持使用多线程来接收、处理客户端命令,因此应用程序可使用连接池来管理Redis连接。 上一章讲的是创建单个连接来操作redis数据库,这次使用连接池来操作redis数据库 Lettuce连接池 支持…...
doris动态分区开启历史分区
举例说明: CREATE TABLE tbl1 (k1 DATE,... ) PARTITION BY RANGE(k1) () DISTRIBUTED BY HASH(k1) PROPERTIES ("dynamic_partition.enable" "true","dynamic_partition.time_unit" "DAY","dynamic_partition.sta…...
Linux用户与权限(认知root用户、修改权限控制 - chmod、修改权限控制 - chown)
目录 1. 认知root用户 1.1 什么是root用户(超级管理员) 1.2 用户切换命令 1.3 sudo命令 1.3.1 为普通用户配置sudo认证 2. 用户、用户组管理 2.1 理解用户、用户组的概念 2.2 掌握用户、用户组管理的相关命令 2.2.1 用户组管理 2.2.2 …...
处理conda安装工具的动态库问题——解决记录 libssl.1.0.0 系统中所有openssl位置全览 whereis openssl
处理conda安装工具的动态库问题——解决记录 处理conda安装工具的动态库问题——解决记录 - 简书 解决libssl.so.1.0.0: cannot open shared object file: No such file or directory问题 - 简书 openssl 默认版本问题(Anaconda相关)_anaconda openssl-…...
如何在Go中格式化字符串
由于字符串通常由书面文本组成,在很多情况下,我们可能希望通过标点符号、换行和缩进来更好地控制字符串的外观,以使其更易于阅读。 在本教程中,我们将介绍一些处理go字符串的方法,以确保所有输出文本的格式正确。 字…...
C程序设计内容与例题讲解 -- 第四章--选择结构程序设计第二部分(第五版)谭浩强
前言:在前面我们学习了选择结构和条件判断,用if语句实现选择结构,关系运算符和关系表达式,逻辑运算符和逻辑表达式等知识。今天我们将接着上一篇未讲完的继续讲解。 鸡汤:种一棵树最好的时间是十年前,其次是现在!加油各…...
接雨水问题
接雨水问题 问题背景 LeetCode 42. 接雨水 接雨水问题是一个经典的计算雨水滞留量的问题,通常使用柱状图来表示不同高度的柱子。在下雨的情况下,柱子之间的凹陷部分能够存储雨水,问题的目标是计算这些柱子所能接收的雨水总量。 相关知识 …...
小谈设计模式(9)—工厂方法模式
小谈设计模式(9)—工厂方法模式 专栏介绍专栏地址专栏介绍 工厂方法模式角色分类抽象产品(Abstract Product)具体产品(Concrete Product)抽象工厂(Abstract Factory)具体工厂&#x…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
使用ch340继电器完成随机断电测试
前言 如图所示是市面上常见的OTA压测继电器,通过ch340串口模块完成对继电器的分路控制,这里我编写了一个脚本方便对4路继电器的控制,可以设置开启时间,关闭时间,复位等功能 软件界面 在设备管理器查看串口号后&…...
