与找硬币的题一样，只不过硬币的面值变成了完全平方数，需要先求出所有硬币的面值。

时间复杂度:$O(n\sqrt{n})$

空间复杂度:$O(n)$

class Solution {
public:
    int numSquares(int n) {
        vector<int> nums;
        int a = sqrt(n);
        for(int i = 1; i <= a; i++){
            nums.emplace_back(i * i);
        }
        int f[n + 1];
        for(int i = 1;i<n+1;i++){
            f[i] = 1e4+10;
        }
        for(int num : nums){
            f[num] = 1;
        }
        for(int i = 1;i<=n;i++){
            for(int num : nums){
                if(i - num >= 1){
                    f[i] = min(f[i], f[i - num] + 1);
                }
            }
        }
        return f[n];
    }
};