279. 完全平方数

题目链接：https://leetcode-cn.com/problems/perfect-squares/
难度：中等

描述：
给你一个整数 n ，返回 和为 _n_ 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

提示：
n: [1, 10000]

题解

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