279.完全平方数

😂BFS

class Solution {
public:
    int numSquares(int n) {
        queue<int> q;
        set<int> s;
        q.push(n);
        int ct = 0;
        while(q.size()) {
            ct++;
            int sz = q.size();
            for(int i = 0; i < sz; ++i){
                int w = q.front();
                q.pop();
                for(int j = 1; j * j <= w; ++j) {
                    int x = w - j * j;
                    if(!s.count(x)) {
                        if(x == 0) 
                            return ct;
                        q.push(x);
                        s.insert(x);
                    }
                }
            }

        }
        return -1;
    }
};

😁动态规划

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