时间限制和数据范围说一下啊，要不然直接四个循环暴力出答案就彳亍（我竟然第一时间就是这么想的）
by Ge_BeatBox_Qy @ 2024-03-27 20:48:52
@
OIer_hjh
by Ge_BeatBox_Qy @ 2024-03-27 20:49:21
@[OIer_hjh](/user/925818) 预处理<=n的所有完全平方数，然后DP
```cpp
#include<iostream>
using namespace std;
int n,a[10005],cnt,dp[1000005];
int main()
{
scanf("%d",&n);
for(int i=0;i*i<=n;i++)a[++cnt]=i*i;
for(int i=0;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
{
dp[j+a[i]]=dp[j]+1;
}
}
printf("%d",dp[n]);
return 0;
}
```
by yinbe2 @ 2024-03-27 23:32:50
@[OIer_hjh](/user/925818) $O(n\sqrt{n})$ 能过吧
by yinbe2 @ 2024-03-27 23:34:30
@[yinbe2](/user/1285691) 这个有问题啊 输入1000输出的0
by OIer_hjh @ 2024-03-29 07:03:01
@[Ge_BeatBox_Qy](/user/726089) 应该是n<=1e5
by OIer_hjh @ 2024-03-29 07:03:52