思路：定义 dp_i 表示和为 i 的完全平方数的最少数量。
边界很明确，当 i 是一个完全平方数时， dp_i=1 。所以，当 n 是一个完全平方数时，就可以直接输出1，而不用dp去推了。
但是转移方程是什么呢？回忆一下，一年级时老师教我们一个整数可以拆分成两个整数之和。所以，我们可以得到转移方程 dp_i=\min_{j=1}^n(dp_j+dp_{n-j})
而数据范围 n\le10^4 ，这种 O(n^2) 的做法已经接近于超时了，所以还要加一个小优化。由于在打擂台时 j\ge \frac{n}{2} 已经重复了，所以转移方程可以优化为 dp_i=\min_{j=1}^\frac{n}{2}(dp_j+dp_{n-j})
再加上 i 为完全平方数的情况，最终状态转移方程如下：
dp_i=\begin{cases}1\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(\lfloor\sqrt{i}\rfloor^2=i) \\ \min_{j=1}^\frac{n}{2}(dp_j+dp_{n-j})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(\lfloor\sqrt{i}\rfloor^2\neq i)\end{cases}
核心代码：
for(int i=1;i<=n;i++){
if(pow((int)sqrt(i),2)==i){
f[i]=1;
continue;
}f[i]=INT_MAX;//初始化为极大值
for(int j=1;j*2<=i;j++)f[i]=min(f[i],f[j]+f[i-j]);
}