完全平方数

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

完全平方数是诸如 1, 4, 9, 16 ... 这样的整数，等于另一个整数的平方。

约定

• 1 <= n <= 10^4

输入

• n：目标整数

输出

最少需要多少个完全平方数相加等于 n。

示例一

输入：

n = 12

输出：

3

解释：12 = 4 + 4 + 4。

示例二

输入：

n = 13

输出：

2

解释：13 = 4 + 9。

复杂度要求

• 时间复杂度：O(n * sqrt(n))
• 空间复杂度：O(n)