279. 完全平方数 - 力扣（LeetCode）

class Solution:
    def numSquares(self, n: int) -> int:
        # 初始化 dp 数组，dp[i] 存储和为 i 的最少完全平方数数量
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 和为 0 的最少完全平方数数量是 0
        
        for i in range(1, n + 1):
            # 遍历所有小于等于 i 的完全平方数
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        
        return dp[n]