给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

思路1：BFS

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

相当于找一条步数最短的路径，使得权重和等于n

思路2：trick

利用四平方和定理：任意一个正整数都能表示成不超过4个整数的平方和。其推论就是：如果一个正整数可以表示成4个整数的平方和，那么也可以表示为 完全平方数 随笔。

综上，问题的答案只有1,2,3,4。先通过推论判断是不是4，再看能不能由1或2个整数的平方和表示，不能的话就返回3.

这里判断能不能由1或2个整数的平方和表示，就是暴力搜索啦，这种写法蛮简洁的

int a = 0;
while(a*a <= n){
    int b = sqrt(n - a*a);
    if(a*a + b*b == n){
        if(a == 0 || b == 0) return 1;
        else return 2;
    }
    a++;
}

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄