class Solution:
    def numSquares(self, n: int) -> int:
        square = [1]
        i = 1
        while True:
            if i **2 < n:
                square.append(i**2)
                i += 1
            elif i ** 2 == n:
                return 1
            else:
                break
        t = i-1
        dp = [0]*(n+1)
        j = 1
        for i in range(1,n+1):
            if j +1 <= t  and square[j+1] <= i:
                j += 1  
            mindp = dp[i-square[j]]
            for k in range(j,0,-1):
                mindp = min(dp[i-square[k]],mindp)
            dp[i] = mindp + 1
        return dp[n]

动态规划 中等 👆动态规划的枚举方法

答案给了五种做法，这是其中第二种

下面是顶级的数学法

class Solution:
    def isSquare(self, n: int) -> bool:
        sq = int(math.sqrt(n))
        return sq*sq == n

    def numSquares(self, n: int) -> int:
        # four-square and three-square theorems
        while (n & 3) == 0:
            n >>= 2      # reducing the 4^k factor from number
        if (n & 7) == 7: # mod 8
            return 4

        if self.isSquare(n):
            return 1
        # check if the number can be decomposed into sum of two squares
        for i in range(1, int(n**(0.5)) + 1):
            if self.isSquare(n - i*i):
                return 2
        # bottom case from the three-square theorem
        return 3