# 279 - Perfect Squares
###### tags: `Medium`

* Question :https://leetcode.com/problems/perfect-squares/

* Key:
1. Dynamic programming
2. BFS
從1(第一個square)加入queue，並以小於目標n開始遍尋，每次累加一個square，然後確認是否等於目標，如果大於目標，代表目前這個數已經不可能再累加出目標，所以將它從queue移除，並且再從queue中挑一個square(perfect square)進行累加，直到嘗試出目標組合的perfect square

- 這題DP用到的空間複雜度比較低，時間複雜度DP也略勝BFS

## DP Solution

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

## BFS Solution

class Solution {
public:
    int numSquares(int n) {
        // Declare data structure for BFS
        unordered_set<int> visited;
        queue<int> todo;

        todo.push(0);
        visited.insert(0);

        // Start BFS
        int steps = 0;
        while(!todo.empty()) {
            ++steps;

            for(int sz = todo.size() - 1; sz >= 0; --sz) {
                // Retrieve current int
                int cur = todo.front();
                todo.pop();

                for(int j = 1; j < n; ++j) {
                    int sum = cur + j * j;

                    if(sum == n) { return steps; }
                    else if(sum > n) { break; }
                    else{
                        if(!visited.count(sum)) {
                            todo.push(sum);
                            visited.insert(sum);
                        }
                    }
                }
            }
        }

        return steps;
    } 
};