python dp solution


  • 0
    X
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            dp = [float('inf')]*(n+1)
            dp[0]=0
            count = 2
            for i in range(1,n+1):
                if i>=count*count:
                    count += 1
                for j in range(1,count):
                    dp[i] = min(dp[i],dp[i-j*j]+1)
            return dp[n]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.