1 题目
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
2 解析
状态：f[i]表示最少需要多少个数的平方来表示整数 i。
这些数必然落在区间。我们可以枚举这些数，假设当前枚举到 jj，那么我们还需要取若干数的平方，构成$i-j^2$。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。
$f[i]=1+\min_{j=1}^{\lfloor\sqrt{i}\rfloor}{f[i-j^2]} $
其中 f[0]=0为边界条件，实际上我们无法表示数字 0，只是为了保证状态转移过程中遇到 j恰为 i \sqrt{i} i 的情况合法。
3 Python实现
class Solution:
def numSquares(self, n: int) -> int:
f = [0]*(n+1)
for i in range(1,n+1):
j = 1
minn = float('inf')
while j*j <=i:
minn = min(minn,f[i-j*j])
j+=1
f[i] = minn+1
return f[n]
