279. Perfect Squares

# Medium

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)

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.

C++

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];
        
    }
};

Second Tab