# 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

# Solution

Approach 1: DP (cache results in a class variable to speed things up).

# Code (Python)

Approach 1:

class Solution:
    # have to use the class variable to speed things up :(
    squares = [0, 1]
    
    def numSquares(self, n: int) -> int:
        # squares[v] -- least num of square numbers that sums up to v. Want squares[n]. Time: O(N * sqrt(N))
        squares = self.squares # refer to the class variable with self.var
        while len(squares) <= n:
            v = len(squares)
            i = int(v ** 0.5)
            min_squares = float('inf')
            while i >= 1:
                min_squares = min(min_squares, 1 + squares[v - i * i])
                if min_squares == 1: # early termination because num squares can't be less than 1
                    break
                i -= 1
            squares.append(min_squares)
        return squares[n]

# OR with memoization
class Solution:
    values = {0:0}
    
    def numSquares(self, num: int) -> int:
        if num < 0:
            raise ValueError
        values = self.values
        if num in values:
            return values[num]
        int_square_root = math.floor(num ** 0.5)
        if int_square_root ** 2 == num:
            values[num] = 1
            return 1
        result = num
        for i in range(int_square_root, 0, -1):
            result = min(result, 1 + self.numSquares(num - i ** 2))
            values[num] = result
        return result

# Code (C++)

Approach 1:

class Solution {
private:
    unordered_map<int,int> umap;
public:
    int numSquares(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (umap.find(n) != umap.end())
            return umap[n];
        int min = n;
        int i = sqrt(n);
        for (; i > 0; --i)
        {
            int res = numSquares(n - i * i) + 1;
            if (res < min)
                min = res;
        }
        umap[n] = min;
        return min;
    }
};

class Solution {
public:
    int numSquares(int n) {
        vector<int> nums = vector<int>(n+1, n);
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            int s = sqrt(i);
            if (s * s == i)
            {
                nums[i] = 1;
                continue;
            }
            for (int j = 1; j <= s; ++j)
            {
                nums[i] = std::min(nums[i], nums[i - j * j] + 1);
            }
        }
        return nums[n];
    }
};