前言

作者：晓宜 ，大厂准入职小白

最近毕业论文快搞完了，打算把之前坚持的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+min1≤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] * (n+1)
          dp[1] = 1
          for i in range(2,n+1):
              val = inf
              j = 1
              while j*j <= i:
                  val = min(val,dp[i-j*j])
                  j+=1
              dp[i] = val+1
          return dp[n]