6676: DP43 最少的完全平方数
[Creator : ]
Description
给定一个正整数 $n$，请找出最少个数的完全平方数，使得这些完全平方数的和等于 $n$。
完全平方指用一个整数乘以自己例如 $1*1,\ 2*2,\ 3*3$ 等，依此类推。
若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如：$1,4,9$ 和 $16$ 都是完全平方数，但是 $2,3,5,8,11$ 等等不是。
完全平方指用一个整数乘以自己例如 $1*1,\ 2*2,\ 3*3$ 等，依此类推。
若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。例如：$1,4,9$ 和 $16$ 都是完全平方数，但是 $2,3,5,8,11$ 等等不是。
Input
仅一行，输入一个正整数 $n$。
Output
按题目要求输出完全平方数之和为n的最少个数。
Constraints
$1 \leq n \leq 10^4$
Sample 1 Input
5
Sample 1 Output
2
1+4=5
Sample 2 Input
8
Sample 2 Output
2
4+4=8
Sample 3 Input
9
Sample 3 Output
1
$3^2=9$