Given a positive integer n, find the least number of perfect square numbers
(for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

算法思想

动态规划。当然我们会首先尝试贪心，例如12，贪心的结果是12=9+1+1+1，可见贪心不能得到最优解，所以只能上动规了。关于动规，思想和编码都不难，不过我想结合编码讨论一下设计模式的东西，也就是在面向对象编程中如何设计一个函数，使函数调用更加高效，其中也涉及一些内存使用优化的问题，开另一篇文章讨论。
数学方法。一个会数学的程序猿可以变身金刚…数学对于效率的提升不能更酷，运行时间先卖个关子，最后再给出。
广度优先搜索。最少个数，对应空间搜索树的最小深度，很多类似的最小问题都可以用广度优先搜索解决，不过这题BFS并不适合，效率不高，代码较长，且有很多细节容易出错，不建议使用。

编码与解释

1. 动态规划：见另一篇文章。

2. 数学方法。

四平方定理：每个正整数均可表示为4个整数的平方和。
更多：https://zh.wikipedia.org/wiki/四平方和定理
三平方定理：每个自然数均可表示为3个整数的平方和，当且仅当该数不能表示为n=pow(4,a)*(8b+7),a,b是整数。
更多https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem

有了两个定理后，作为一个菜鸡程序员，应该也能搞定代码。注意两个小细节：
1.使用&,==等不明确优先级的运算符时，最好加上括号！
2.不要忘记单独对结果为2时的判断，见代码注释处//check

//cpp
class Solution {
public:
    int numSquares(int n) {
        if(n<=0) return 0;
        if(isSqure(n)) return 1;
        while((n&3)==0) n>>=2;
        if((n&7)==7) return 4;
        int sqrt_n=(int)sqrt(n);
        for(int i=1;i<=sqrt_n;++i){//check
            if(isSqure(n-i*i)) return 2;
        } 
        return 3;
    }
    bool isSqure(int n)
    {
        int sqrt_n=(int)sqrt(n);
        return sqrt_n*sqrt_n==n?1:0;
    }
};

3.广度优先搜索

搜索树大致形状：

             0 
  1       4      9     16
2 5...   5...  10..  17...

无论是广度优先还是深度优先(回溯常用)，关键都是要画出空间搜索树。三个细节要注意：
注释1：提高效率，跳过同层已计算过的节点。
注释2：为什么不能使用else？结合空间搜索树考虑，else的情况包括cur+i<n&&num[cur+i-1]!=0，什么意思呢，表示该节点对应的该值在之前已经考虑过，但是能直接从这里break吗？不能！因为该值只是被计算过，不代表该节点右边的兄弟节点应该被跳过。这些兄弟节点仍然应该被计算。
注释3：队列q.pop()的在循环中的正确位置

//cpp
class Solution {
public:
    int numSquares(int n) {
        if(n<=0) return 0;
        vector<int> num(n,0);
        vector<int> ps;
        for(int i=1;i<=n/i;++i)
        {
            ps.push_back(i*i);
            num[i*i-1]=1;
        }
        if(ps.back()==n) return 1;
        queue<int> q;
        for(int &i:ps) q.push(i);
        int numSq=1;
    while(!q.empty())
    {
        ++numSq;
        int size=q.size();
            while(size--)
            {
                int cur=q.front();
                for(int &i:ps)
                {
                    if(cur+i==n) return numSq;
                    else if(cur+i<n&&num[cur+i-1]==0)//1
                    {
                        q.push(cur+i);
                        num[cur+i-1]=numSq;
                    }
                    else if(cur+i>n) break;//2
                }
                q.pop();//3
            }
        }
        return numSq;
    }
};

运行时间对比(600 test cases)：

动态规划(优化版)	数学	广度优先
16ms	3ms	68ms