力扣 -- 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…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
