🐰😺🔲 兔猫信奥学院的魔法平方探秘 🔲😺🐰

在信奥学院深处的数学秘境中，加菲老师对小兔和小猫提出了一个有趣的魔法考验：

“给你一个整数 (n)，请找出最少需要多少个完全平方数（如 (1,4,9,16,\dots)）相加，才能和为 (n)？”

他们兴奋地掀开魔法石碑，开始破解这道古老的数阵之谜。

输入格式

输入一行，包含一个正整数 n。

• (1 \le n \le 10^4)

输出格式

输出一个整数，表示和为 n 的完全平方数的最少数量。

12

3

解释：
(12 = 4 + 4 + 4)，共 3 个完全平方数。

13

2

解释：
(13 = 4 + 9)，共 2 个完全平方数。

🎓 加菲老师寄语：
利用“动态规划+完全背包”策略，你可以在 (O(n\sqrt n)) 时间内迅速求得最少完全平方数个数。祝探秘愉快，算法更进一步！