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+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] = 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]