DP and Recursive solution for Python


  • 0
    C
    import sys
    class Solution(object):
        def numSquares(self, n):
            """
            :type n: int
            :rtype: int
            """
            self.perfectSquares = self.getPerfectSquares(n)
            return self.numSquaresDP(n)
        def getPerfectSquares(self, n):
            perfectSquares = [1]
            for i in range(2, int(pow(n, .5))+1):
                perfectSquares.append(pow(i, 2))
            return perfectSquares
                
            
        def numSquaresRecursive(self, n):
            if n == 0:
                return 0
            minSteps = sys.maxint
            for square in self.perfectSquares:
                if n - square >=0:
                    minSteps = min(minSteps, 1+self.numSquaresRecursive(n-square))
            return minSteps
        
        def numSquaresDP(self, n):
            cache = [sys.maxint] * (n+1)
            cache[0] = 0
            for i in range(0, len(cache)):
                if cache[i] != sys.maxint:
                    for square in self.perfectSquares:
                        if i+square<=n:
                            cache[i+square] = min(1+cache[i], cache[i+square])
            return cache[n]
    

Log in to reply
 

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