# 279. Perfect Squares

{% hint style="info" %}
Two methods:

1. Lagrange's four square theorem. All numbers can be decompited to at most 4 squares `(1, 2, 3, 4)`.
2. DP solution. (Take a lot of energy to optimize time complexity)
   {% endhint %}

### Optimize solution:

1. Initialize all squares' `count` with `-1`.
2. Initialize all known squares, like cheating table. If `count[x] = -1`, then number x is not a square.
3. Only the number who is not a square is needed to compute. 
4. If this number can be decomposeted into two squares, then `count[x] = 2`. Ohterwise continue computing using `DP` method.

{% tabs %}
{% tab title="C++" %}

```cpp
class Solution {
public:
    int numSquares(int n) {
        int count[n+1]; // store count of each number from 1 to n
        // initialize
        for(int i = 1; i <= n; i ++) {
            count[i] = -1;
        }
        
        for(int i = 0; i <= n; i ++) {
            if(i*i <= n) {
                count[i*i] = 1;
            } else{
                break;
            }
        }
        
        // DP solve this
        for(int x = 1; x <= n; x ++) {
            if(count[x] == -1) {
                count[x] = x;
                // decomposite number x
                for(int i = 1; i <= x/2; i ++) {
                    if(count[i] == 1 and count[x-i] == 1) {
                        count[x] = 2;
                        break;
                    } else if(count[i] != 1 and count[x-i] != 1) {
                        continue;
                    } else {
                        count[x] = min(count[i]+count[x-i] < count[x]);
                    }
                }                
            }
        }
        
        return count[n];
        
    }
};
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}