# 279. Perfect Squares
#### Difficulty: Medium
link: https://leetcode.com/problems/perfect-squares

### 1. DP
#### $O(n \sqrt n)$ runtime, $O(n)$ space

用`dp[i]`來代表`numSquares(i)`的解，n扣掉一個平方數後，找出前面i用最少平方數的解。

Note: 實作上，盡量避免使用時間複雜度是 $O(log(n))$ 的`sqrt()`，用`j * j <= n`而不是`j <= sqrt(i)`。

##### C++

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], 1 + dp[i-j*j]);
            }
        }
        return dp[n];
    }
};

### 2. Math
#### $O(\sqrt n)$ runtime, $O(\sqrt n)$ space

#### a. Legendre's three-square theorem
Let $n$ be a natural number. $n=x^2 + y^2 + z^2$ is solvable in non-negative number
  $\iff$ $n$ is not of the following form: $4^a(8b+7)$

#### b. Lagrange's four-square theorem
Every natural number can be represented as a sum of four non-negative integer squares.

根據以上兩個理論，正整數最多只會由4個平方數組成。只要不是$4^a(8b+7)$的形式，都可由<=3個平方數組成。

Note: 第5行`n /= 4`不影響平方數的個數，因為 $4=2^2$ 也是平方數。

##### C++

class Solution {
public:
    int numSquares(int n) {
        //Use Lagrange's four-square theorem and Legendre's three-square theorem
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;

        unordered_set<int> square;
        for (int i = 1; i * i <= n; ++i) {
            square.insert(i * i);
        }

        if (square.count(n)) return 1;
        for (int i = 1; i * i <= n; ++i) {
            int j = n - i * i;
            if (square.count(j)) return 2;
        }
        return 3;
    }
};

###### tags: `leetcode`