279. 完全平方数

给定正整数 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

动态规划 中等

动态规划方法重做完全平方数

代码

class Solution:
    def __init__(self):
        self.POWER = []
        for i in range(101):
            self.POWER.append(i * i)
    def numSquares(self, n: int) -> int:
        for p, num in enumerate(self.POWER):
            # if num == n:
            #     return 1
            if num >= n:
                break
        dp = [ i for i in range(n+1)] # 只用数字1情况
        for i in range(2, p+1):
            t = self.POWER[i]
            for j in range(t, n+1):
                dp[j] = min(dp[j], dp[j-t]+1)
        return dp[n]