Minimum perfect squares needed to sum up to a target I'm trying to solve this problem


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


I've come up with a solution that works correctly but times out on large inputs:

from collections import defaultdict
class Solution:
    def numSquares(self, n: int) -&gt; int:
        coins = []
        for i in range(1, n+1):
            if i**2&gt;n:
                break 
            coins.append(i**2)
        min_coins_to_make = defaultdict(lambda :float("inf"))
        min_coins_to_make[0] = 0 
        for coin in coins:
            if coin &gt; n:
                break 
            for target in range(coin, n+1):
                min_coins_to_make[target] = min(min_coins_to_make[target], 1+min_coins_to_make[target-coin])
        if min_coins_to_make[target] == float("inf"):
            return 0 
        return min_coins_to_make[target]



How do I optimize it in terms of time and space complexity?

https://leetcode.com/problems/perfect-squares/
I won't specifically address the execution time concerns to begin with; there are other issues:

Don't use a class

There's no reason for this to be a class. You have one method and you don't even reference self. In theory you could remove self and mark it a @staticmethod, but really it should just be a function without a class.

Reuse variables

Make this variable -

i2 = i**2


since it's used twice. The same goes for min_coins_to_make[target].

Loop limit

    for coin in coins:
        if coin &gt; n:
            break 


That termination condition will be true if coin &gt; n, but coin == i**2. i**2 &gt; n will never be true, because in the previous loop,

        if i**2&gt;n:
            break 


So can't you just write for coin in coins without an interior termination condition?