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

前言

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

Problem: 279. 完全平方数

题目

给你一个整数 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,$\sqrt{x}$] 中的所有数字j，此时：
x有最少多少个完全平方数组成的问题 演变为 x-j*j这个数有最少多少个完全平方数组成+1。我们要想知道x有最少多少个完全平方数组成，就要知道x-j*j这个数有最少多少个完全平方数组成的最小值。

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

$f[i]=1+{\min }_{\begin{array}{c}1\le j\le \lfloor \sqrt{i}\rfloor \end{array}}f[i-j^2]$

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

复杂度

时间复杂度:

两层遍历，但是第二层之遍历了 $\sqrt{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]