LeetCode-279. 完全平方数【广度优先搜索 数学 动态规划】
LeetCode-279. 完全平方数【广度优先搜索 数学 动态规划】
- 题目描述:
- 解题思路一:Python 动态规划五部曲(完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?)
- 解题思路二:0
- 解题思路三:0
题目描述:
给你一个整数 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
解题思路一:Python 动态规划五部曲(完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?)
-
确定dp数组(dp table)以及下标的含义
dp[j]:和为j的完全平方数的最少数量为dp[j] -
确定递推公式
dp[j] 可以由dp[j - i * i]推出, dp[j - i * i] + 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j],所以递推公式:dp[j] = min(dp[j - i * i] + 1, dp[j]);
- dp数组如何初始化
dp[0]表示 和为0的完全平方数的最小数量,那么dp[0]一定是0。
有同学问题,那0 * 0 也算是一种啊,为啥dp[0] 就是 0呢?
看题目描述,找到若干个完全平方数(比如 1, 4, 9, 16, …),题目描述中可没说要从0开始,dp[0]=0完全是为了递推公式。
非0下标的dp[j]应该是多少呢?
从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的,所以非0下标的dp[j]一定要初始为最大值,这样dp[j]在递推的时候才不会被初始值覆盖。
- 确定遍历顺序
我们知道这是完全背包,
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
在动态规划:322. 零钱兑换 (opens new window)中我们就深入探讨了这个问题,本题也是一样的,是求最小数!
所以本题外层for遍历背包,内层for遍历物品,还是外层for遍历物品,内层for遍历背包,都是可以的!
- 举例推导dp数组
已输入n为5例,dp状态图如下:
class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1) # return dp[n]dp[0] = 0for i in range(n+1): # 注意需要dp[n],那么这里需要n+1j = 1while j ** 2 <= i:dp[i] = min(dp[i], dp[i - j ** 2] + 1)j += 1return dp[n]
时间复杂度:O(n)
空间复杂度:O(n)
解题思路二:0
时间复杂度:O(n)
空间复杂度:O(n)
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)
相关文章:

LeetCode-279. 完全平方数【广度优先搜索 数学 动态规划】
LeetCode-279. 完全平方数【广度优先搜索 数学 动态规划】 题目描述:解题思路一:Python 动态规划五部曲(完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品…...

rust项目组织结构和集成测试举例
概述 在学习rust的过程中,当项目结构略微复杂的时候,写集成测试的时候发现总是不能引用项目中的代码,导致编写测试用例失败。查阅了教程,一般举例都很简单。查阅了谷歌和百度以及ai,也没有找到满意的答案。这里记录一…...

软件文档交付清单(直接套用合集)
软件文档交付清单是指在软件开发项目完成后,开发团队需要准备的一份详细清单,用于确保交付的软件产品符合客户需求并达到预期的质量标准。以下是软件文档交付清单中可能包含的一些关键要素 软件开发文档:这包括需求文档、设计文档、测试文档等…...

ModuleNotFoundError: No module named ‘ultralytics.utils‘
项目场景he 问题描述 提示:这里简述项目相关背景: model YOLO(modelr./yolov8m-cls.pt) 加载预训练模型时报错。 ModuleNotFoundError: No module named ultralytics.utils warning: bug: 原因分析: 很可能是提前下载的预训练模型出了…...

2024智能计算、大数据应用与信息科学国际会议(ICBDAIS2024)
2024智能计算、大数据应用与信息科学国际会议(ICBDAIS2024) 会议简介 智能计算、大数据应用与信息科学之间存在相互依存、相互促进的关系。智能计算和大数据应用的发展离不开信息科学的支持和推动,而信息科学的发展又需要智能计算和大数据应用的不断拓展和应用。智…...

秋招复习笔记——八股文部分:操作系统
笔试得刷算法题,那面试就离不开八股文,所以特地对着小林coding的图解八股文系列记一下笔记。 这一篇笔记是图解系统的内容。 硬件结构 CPU执行程序 计算机基本结构为 5 个部分,分别是运算器、控制器、存储器、输入设备、输出设备…...
每日一题:C语言经典例题之杨辉三角
题目描述 输出杨辉三角形。 输入 第一行输入一个整数 n (1<n<10)。 输出 输出杨辉三角形的前n行,每个数字占8格左对齐。 样例输入 4 样例输出 1 1 1 1 2 1 1 3 3 1 代码: #inc…...
1. TypeScript: JavaScript 的超集,为大型应用而生
引言 在现代的前端开发领域,JavaScript 无疑是一门极其流行的语言。然而,随着前端项目的日益复杂,JavaScript 本身的一些特性使得维护和扩展大型代码库变得困难。这就是 TypeScript 应运而生的背景。TypeScript 是一种由微软开发的开源语言&…...

vex-table—— 获取插入或修改数据后的tableData
例子来自vxe-table。在开发过程中发现新增数据后,输出this.tableData,发现数据并没有被修改 想要获取更新的数据方式为 mounted () {const $table this.$refs.xTableconsole.log("🚀 ~ mounted ~ $table:", $table.tableData)},...
通俗易懂地解释Go语言不同版本中垃圾回收机制的演进过程
完整课程请点击以下链接 Go 语言项目开发实战_Go_实战_项目开发_孔令飞_Commit 规范_最佳实践_企业应用代码-极客时间 Go 1.3时代 - 标记清除算法 这就像一个人要打扫房间,首先需要暂停其他活动。然后开始查看房间里的每件物品,对于自己仍需要使用的物品做上记号。查看完毕后…...

shamrockcms代码审计-啥也没有
shamrockcms 环境搭建 使用阿里源,创建数据库,运行shamrockcms.sql文件,将configure.properties中的jdbc修改为自己本地或者其他ip数据库连接,并且将ueditor.config.json中的master修改为localhost或者其他自己设置的ip 危险组件…...

【C++】排序算法 --快速排序与归并排序
目录 颜色分类(数组分三块思想)快速排序归并排序 颜色分类(数组分三块思想) 给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums ,原地对它们进⾏排序,使得相同颜⾊ 的元素相邻,并按照红⾊、…...

(Python)根据经纬度从数字高程模型(DEM)文件获取高度
基本介绍 在地理信息系统(GIS)和遥感中,数字高程模型(Digital Elevation Model,简称DEM)是一种表示 地表或地形高程信息的重要数据。DEM数据通常以栅格(raster)形式存在࿰…...
【WPF应用41】WPF中的Expander控件详解
Windows Presentation Foundation(WPF)中的Expander控件是一个用于显示详细信息的交互式UI元素。它允许用户通过点击标题来展开或折叠内容区域。Expander控件通常用于在界面上组织内容,提供一种可见/隐藏的功能,以帮助用户专注于当…...
golang变量初始化顺序
顺序: 1.引用的包 2.全局变量 3.init()函数 4.main()函数 package pkgimport "fmt"func init() {fmt.Println("pkg init") }package mainimport ("fmt"_ "gg/pkg" )var v val()func val() int {fmt.Println("func()…...
魔众 文库配置异步转换
同步转换 系统默认使用同步转换,即用户上传文档提交接口瞬间,系统会立即进行转换。 同步转换容易造成页面卡顿,转换时间超长的情况下,系统接口会超时。 异步转换 系统支持异步转换,即用户上传文档提交接口瞬间&…...

创建型模式--2.简单工厂模式【人造恶魔果实工厂1】
1. 工厂模式的特点 在海贼王中,作为原王下七武海之一的多弗朗明哥,可以说是新世界最大的流氓头子,拥有无上的权利和无尽的财富。他既是德雷斯罗萨国王又是地下世界的中介,控制着世界各地的诸多产业,人造恶魔果实工厂就…...
一些考研经验
前言 考研结束已有半个月,之前一直想写经验贴,奈何感觉自己本身就比较菜,考了两年才堪堪上岸,所以有些犹豫,拖拖沓沓到现在,思虑再三最终决定把自己对于考研的一些拙见记录一下,供各位参考。 …...

StockTrading AI小模型股票自动交易系统 转载
Stock-Trading StockTrading AI小模型股票自动交易系统 项目文档 Stock-Trading 语雀 项目展示 功能介绍 对接证券平台,实现股票自动化交易使用QuartZ定时任务调度,每日自动更新数据使用DL4J框架实现LSTM模型指导股票买入,采用T1短线交易策…...

01背包问题合集 蓝桥OJ
一、蓝桥OJ 1174小明的背包1 模板题 思路: 用二维数组dp判断最大价值,i表示物品数量,j表示物品体积,如果 j > V 则无需继续, j > w 物品还能再增加,同样价值也增加,否则继承之前的价值&am…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...