//四平方和定理
int numSquares(int n) {
while(n%4==0)
n=n/4;
if(n%8==7)
return 4;
for(int i=0;i*i<n;i++)
{
int b=sqrt(n-i*i);
if(i*i+b*b==n)
return !!i+!!b;
}
return 3;
}
//dp方法
int numSquares(int n) {
vector<int> dp(n+1);
for(int i=0;i<=n;i++)
dp[i]=i;
for(int i=2;i<=n;i++)
{
for(int j=1;j*j<=i;j++)
dp[i]=min(dp[i],dp[i-j*j]+1);
}
return dp[n];
}
利用四平方和定理，即每个正整数都可以由至多4个整数的平方和相加得到，
并且当该数由四个组成时，n=4^a*(8*b+7);所以我们可以先不断除以四缩小n，因为4是平方数，所以除以4不影响结果，然后判断即可。
原文：https://www.cnblogs.com/QingFengDaHui/p/10452862.html