给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。

完全平方数是一个整数其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而3和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

思路1：dfs

嗯显然我除了深搜就啥也不会了

class Solution:
    def __init__(self):
        self.nums = []
        self.ans = 10000
    def numSquares(self, n: int) -> int:
        self.nums = [i*i for i in range(100,0,-1)]
        self.dfs(n,0,0)
        return self.ans

    def dfs(self,remain,step,itr_start):#剪枝1
        if step >= self.ans: #剪枝2
            return
        if remain == 0:
            self.ans = step
            return
        for i in range(itr_start,len(self.nums)):
            if self.nums[i] <= remain:
                self.dfs(remain-self.nums[i],step+1,i)

不过这个深搜不算特别无脑，还是有两处剪枝的。(数据量这么大用脚想也知道直接dfs会超时)

第一处剪枝:保留上一次访问的下标。因为在这个下标之前的一定已经深搜过一遍了。
第二处剪枝:当step已经大于ans，就肯定更新不了ans的值了，所以直接return

用时大概在前44%，其实效果还不错

思路2：dp

比较简单的dp，我以为会超时，但其实还好。

class Solution:
    def __init__(self):
        self.squre_nums = []
        self.dp = []
    def numSquares(self, n: int) -> int:
        self.squre_nums = [i*i for i in range(1,101)]
        self.dp = [i for i in range(n+1)]
        for i in range(n+1):
            for squre_num in self.squre_nums:
                if squre_num > i:
                    break
                self.dp[i] = self.dp[i] if (self.dp[i] < (self.dp[i-squre_num]+1)) else (self.dp[i-squre_num]+1)
        return self.dp[n]

初始值:dp[i] = i:即仅使用1相加的情况。
转移方程：dp[i] = min(dp[i], dp[i-squre_num]+1)
注意这里的squre_num是完全平方数，需要遍历100个数才能确定
用时在前70%