279. Perfect Squares

這題蠻厲害的, 一個很好的轉變成ｂｆｓ， 我覺得我沒辦法說得很詳細我直接貼連結

https://blog.csdn.net/myrealization/article/details/108228497

要注意, 不要將同樣的節點放進queue裡, 否則他每個在算就TLE了

class Solution {
public:
    int numSquares(int n) {
        int step = -1;
        queue<int>q;
        q.push(n);
        unordered_set<int> visited;
        while(!q.empty()){
            int size = q.size();
            step++;
            for(int i = 0; i < size; i++){
                int num = q.front();
                q.pop();
                if(num == 0)return step;
                for(int j = 1; num - j * j >=0 ;j++){
                    if(visited.count(num - j * j )){
                        continue;
                    }
                    q.push(num -j*j);
                    visited.insert(num -j*j);
                }
            }
            visited.clear();
        }
        return step;
    }
};

後記, 上面那個要當下想到我覺得有點點的困難

我覺得dp的實現可能會容易些,

我們先把平方的數直接就設為1, 並記錄是哪些人,

接著我們遍歷整個數的所有值, 每個人都去配對平方數, 一旦有一個更小的可能, 我們就去替換掉

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