LC 279完全平方数Perfect Squares　中等

求和为 n 的完全平方数的最少个数（可重复使用同一平方数）。

思路 完全背包：dp[i] = min(dp[i - j*j] + 1)，枚举所有不超过 i 的平方数。时间 O(n·√n)。

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [inf] * n
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]