小杨和整数拆分
EXY-PG-0167
题目描述
小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
编程计算总和为 $n$ 的完全平方数的最小数量。
输入格式
输入只有一行一个正整数 $n$。
输出格式
输出一行一个整数表示答案。
样例说明
样例 1
输入：
18
输出：
2
样例解释：
18 = 9+9 = 16+1+1，其中最少需要 2 个完全平方数。
数据范围
对于全部数据，保证有 $1 \leq n \leq 10^5$。