Find smallest number of squares that sum to a number Leetcode problem 279 “Perfect Squares” is:


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


I wrote the following solution:

def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        sqs = [0]
        nums = {}
        for x in range(1,n+1):
            nums[x] = 1
        for i in nums:
            if (i * i) in nums:
                sqs.append(i * i)              
        T = [x for x in range(n+1)]
        for i in range(1,len(sqs)):
            for j in range(1,n+1):
                if sqs[i] &lt;= j:
                    T[j] = min(T[j],math.floor(j/sqs[i]) + T[j%sqs[i]])
        return T[n]


I wrote a dynamic-programming solution, storing results in a 1d array, but it seemed that due to the way I was originally calculating the perfect squares, the solution was timing out. I then modified the solution and came up with the one above, but the code is still causing a time out error when run against an input of 4635 for n.

How could this solution be optimized to avoid this timeout error?
Not an review, but an extended comment:

I don't know how this solution can be optimized. The expected solution is radically different, and is based on a couple of theorems from number theory.

You should check whether the number is


A perfect square (the answer is obviously 1), or
is a sum of 2 squares (the answer is obviously 2), or
not a Legendre's number, that is \$n = 4^a(8b + 7)\$ (the answer is 3)


Otherwise, the answer is 4.