题解 | #完全平方数的草料#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 定义一个数组 dp，其中 dp[i] 表示构成数字 i 所需的最小完全平方数数量。
2. 然后，我们从 1 到 n 枚举每一个数字 i，计算其对应的 dp 值。具体来说，对于每个数字 i，我们枚举所有小于等于它的完全 平方数 j^2，然后计算 dp[i-j^2]+1 的最小值。这个最小值即为 dp[i] 的值。
3. 最后，我们可以通过倒推的方式，从 dp[n] 开始向前找到第一个满足条件的完全平方数，并将其加入结果列表。然后更新当前数字为 n 减去这个完全平方数的差，继续寻找下一个完全平方数，直到 n 等于 0。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型一维数组
#
import math

class Solution:
    def numSquares(self , n: int) -> List[int]:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                if j * j <= i:
                    dp[i] = min(dp[i], dp[i - j * j] + 1)
        ans = []
        i = n
        while i > 0:
            for j in range(int(math.sqrt(i)), 0, -1):
                if dp[i] == dp[i - j * j] + 1:
                    ans.append(j * j)
                    i -= j * j
                    break
        return sorted(ans)