您的位置:首页 > 文旅 > 旅游 > leetcode热题100.完全平方数(动态规划进阶)

leetcode热题100.完全平方数(动态规划进阶)

2024/12/23 15:55:20 来源:https://blog.csdn.net/qq_51118755/article/details/139130215  浏览:    关键词:leetcode热题100.完全平方数(动态规划进阶)

前言

作者:晓宜 ,大厂准入职小白
最近毕业论文快搞完了,打算把之前坚持的hot100系列文章更完,帮助大家更好的通过面试和笔试,都拿到大厂offer,大家快跟着刷起来呀。
从今天起立一个flag,每天更新一篇算法,直到这个系列跟新完毕!大家可以跟着晓哥一起刷,争取秋招进大厂!!!🌈🌈🌈

Problem: 279. 完全平方数

文章目录

  • 前言
  • 题目
  • 思路
  • 复杂度
  • Code

题目

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

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:

输入:n = 12

输出:3

解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13

输出:2

解释:13 = 4 + 9

思路

题目给了我们一个n,要求我们求出m个完全平方数相加可以得到这个数字n的m的最小值。

我们假设现在有一个数x,x<=n,我们要求最少的完全平方数可以相加得到x,此时我们可以枚举 [1, x \sqrt{x} x ] 中的所有数字j,此时:
x有最少多少个完全平方数组成的问题 演变为 x-j*j这个数有最少多少个完全平方数组成+1。我们要想知道x有最少多少个完全平方数组成,就要知道x-j*j这个数有最少多少个完全平方数组成的最小值。

根据这样的关系,我们发现了x的状态可以由他之前的状态推导出来,我们定义 f [ i ] f[i] f[i] 的值为数字i最少有多少个完全平方数组成,我们可以得到这样的公式:

f [ i ] = 1 + min ⁡ 1 ≤ j ≤ ⌊ i ⌋ f [ i − j 2 ] f[i] = 1 + \min_{\substack{1 \le j \le \lfloor \sqrt{i} \rfloor}} f[i - j^2] f[i]=1+min1ji f[ij2]

在程序最开始的时候,1只能由1这个完全平方数组成,我们给f[1] 赋值为 1,在接下来的算法中,我们每次经过x,都要回去找x-j*j的最小组成个数,找到这个数字之后+1,就是x的完全平方数的最小组成数。

复杂度

时间复杂度:

两层遍历,但是第二层之遍历了 n \sqrt{n} n 次: O ( n ) O(n) O(n)

空间复杂度:

O ( n ) O(n) O(n)

Code

class Solution:def numSquares(self, n: int) -> int:dp = [0] * (n+1)dp[1] = 1for i in range(2,n+1):val = infj = 1while j*j <= i:val = min(val,dp[i-j*j])j+=1dp[i] = val+1return dp[n]

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com