Perfect squares

'''
For a number n, we only need to consider numbers from 1 to sqrt(n) because any number larger than sqrt(n) will have a square greater than n and therefore cannot contribute to the sum. For example, if n = 25, then the possible numbers are 1, 2, 3, 4, 5, whose squares are 1, 4, 9, 16, 25. The problem then becomes finding the minimum number of these square values whose sum equals n. So this problem is essentially similar to the Minimum Coin Change or Minimum Denominations problem, where the square numbers act like coins and we need the minimum number of coins to form the target sum.'''

import math
def fun(index,current_sum,numbers,dp,target):
    if current_sum==target:
        return 0

    if index<0 or current_sum>target: #as this is not a valid case
        return math.inf

    if dp[index][current_sum]!=-1:
        return dp[index][current_sum]

    take=math.inf
    square=numbers[index]*numbers[index]
    if current_sum+square<=target:
        take=1+fun(index,current_sum+square,numbers,dp,target)

    not_take=fun(index-1,current_sum,numbers,dp,target)
    dp[index][current_sum]=min(take,not_take)
    return dp[index][current_sum]


class Solution:
    def numSquares(self,n):
        r=int(sqrt(n))
        numbers=[i for i in range(1,r+1)]
        dp=[[-1]*(n+1) for _ in range(limit)]
        return fun(r-1,0,numbers,dp,n)