Question 279. Perfect Squares

Link:

https://leetcode.com/problems/perfect-squares/

My Code:

class Solution:
    def numSquares(self, n: int) -> int:
        if n ==1:
            return 1
        else:
            NumList = [0]
            for Number in range(1,n+1):
                Min = 2**31
                SquareNum = math.floor(math.sqrt(Number))
                for j in range(1,(SquareNum+1)):
                    Min = min(Min,NumList[Number-j**2])
                NumList.append((Min+1))
            return NumList[n]

Explanation

It is clear that we for number a , we may check the number squares the a-k is made of and then take the minimum among them. A typical dynamic programming problem.