这道题目看似平平无奇，AC的过程中遇到了不少坑。
首先我们按照最直观、最快速的解法来写代码：

class Solution {
public:
    int numSquares(int n) {
        int sum = 0;
        int num = n;
        int cnt = 0;
        while(num > 0) {
            while(n >= sum + num && is_squares(num))
            {
                sum += num;
                cnt += 1;
                if(sum == n) return cnt;
            }
            num--;
        }
        return cnt;
    }
private:
    bool is_squares(int n){
        int num = sqrt(n);
        if(num * num == n)
            return true;
        return false;
    }
};

发现WA：

Submission Detail
312 / 588 test cases passed.
Status: Wrong Answer
Submitted: 4 minutes ago
Input:
12
Output:
4
Expected:
3

说明我们的贪心策略是无法解决这类问题的，例如上面的12，正确的解法应该是4+4+4.
而我们给出得答案是9+1+1+1.
上面代码另一个需要注意的地方是函数is_squares，最开始我写成了：

bool is_squares(int n){
    if(sqrt(n) * sqrt(n) == n)
        return true;
    return false;
    }

这里输入11返回了true,而正确的解法应该是将sqrt返回的结果赋值给int。
那么如何解决12这个场景下最少数据的个数呢?这个时候很自然的想到了动态规划。
首先定义dp[i]表示对数字i来说最少需要多少个完全平方数来构成。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i = 1;i<=n;i++)
        {
            for(int j = 1;j*j <= i;j++)
                dp[i] = min(dp[i],dp[i-j*j] + 1);
        }
        return dp[n];
    }
};

动态规划的解法比较简单，如果想不明白可以借助下图：

例如dp[25]=dp[25-4*4] + 1,因为4是完全平方数，所以我们加1，这样将dp[25]转换为求解dp[9]，而dp[9]=dp[9-3*3] + 1= dp[0] + 1 = 1，我们是按照逆序求解，可以通过递归的方式实现，而我们通过爬楼梯问题也知道正向求解（从小到大）效率更高，避免了重复子问题的计算。
因此，从形式上来看一定是两层循环，第一层循环是我们计算从dp[1]到dp[n]的值，内层循环是计算dp[i]的具体值。这里假设i-k（k是完全平方数，并且k小于i)。
运行效率:

Runtime: 184 ms, faster than 53.88% of C++ online submissions for Perfect Squares.
Memory Usage: 9 MB, less than 66.35% of C++ online submissions for Perfect Squares.

BFS方式实现

class Solution {
public:
    int numSquares(int n) {
        //去重 保存已求得的和
        unordered_set<int> visited;
        queue<int> q;
        //保存小于等于n的完全平方数
        vector<int> perfect;
        int step = 1;
        for(int i = 1;i*i<=n;i++)
        {
            int num = i*i;
            q.push(num);
            perfect.push_back(num);
            visited.insert(num);
        }
        //如果最后一个元素等于n，则只需要一个
        if(q.back() == n) return 1;
        
        while(!q.empty())
        {
            step += 1;
            int size = q.size();
            for(int i = 0;i < size;i++)
            {
                int num = q.front();
                for(auto elem : perfect)
                {
                    //遍历完全平方数vector，每次相加判断和n的关系
                    int sum = num + elem;
                    if(sum > n) break;
                    if(sum == n) return step;
                    if(sum < n && !visited.count(sum))
                    {
                        visited.insert(sum);
                        q.push(sum);
                    }
                }
                q.pop();
            }
        }
        
        return -1;
    }
};

运行效率:

Runtime: 112 ms, faster than 74.35% of C++ online submissions for Perfect Squares.
Memory Usage: 26.2 MB, less than 11.14% of C++ online submissions for Perfect Squares.