from math import floor, sqrt

class Solution:
    def get_min_square_count(self, n):
        if n == 0:
            return 0
        memo = [-1 for _ in range(n + 1)]
        memo[0] = 0

        return self.get_min_square_rec(memo, n)
    
    def get_min_square_rec(self, memo, n):
        if memo[n] < 0:
            biggest_square = floor(sqrt(n)) ** 2
            memo[n] = (n // biggest_square) + self.get_min_square_rec(memo, n % biggest_square)
        
        return memo[n]

    def get_min_squares(self, n):
        memo = [0] + [float('inf') for _ in range(n)]
        
        for i in range(1, n + 1):
            min_count = float('inf')
            j = 1
            while i - j*j >= 0:
                min_count = min(min_count, 1 + memo[i - j * j])
                j += 1
            
            memo[i] = min_count
        
        return memo[-1]

solution = Solution()
for i in range(10):
    print("n = {} : {}".format(i, solution.get_min_square_count(i)))
    print("n = {} : {}".format(i, solution.get_min_squares(i)))