279. 完全平方数

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

描述：
给你一个整数 n ，返回 和为 _n_ 的完全平方数的最少数量 。

题解

class Solution:
    def numSquares(self, n: int) -> int:
        # r[i]是和为i的完全平方数的最少数量
        r = list(range(n+1))
        for i in range(1, n+1):
            j = 1
            while j * j <= i:
                r[i] = min(r[i], 1 + r[i - j*j])
                j += 1
        return r[-1]