男人和女人晚上做污污的视频大网站,站内推广途径,网站建设免费书,服装设计手绘前言 作者#xff1a;晓宜 #xff0c;大厂准入职小白 最近毕业论文快搞完了#xff0c;打算把之前坚持的hot100系列文章更完#xff0c;帮助大家更好的通过面试和笔试#xff0c;都拿到大厂offer#xff0c;大家快跟着刷起来呀。 从今天起立一个flag#xff0c;每天更新…前言 作者晓宜 大厂准入职小白 最近毕业论文快搞完了打算把之前坚持的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的最小值。
我们假设现在有一个数xxn,我们要求最少的完全平方数可以相加得到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]1min1≤j≤⌊i ⌋f[i−j2]
在程序最开始的时候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] * (n1)dp[1] 1for i in range(2,n1):val infj 1while j*j i:val min(val,dp[i-j*j])j1dp[i] val1return dp[n]
