A/C Python solution, DP, easy to understand, beat 11%


  • 0
    W
    def numSquares(self, n):
        #print "numSquares, n = ", n
        squareNumbers = []
        i = 1
        dpMatrix = [0 for i in range(n+1)]
    
        j = 0
        squareNumbers = [1]
        for i in range(1, n+1):
            #print "i = ", i, " dpMatrix = ", dpMatrix
    
            while j*j <= i:
                squareNumbers.append(j*j)
                j += 1
    
            #print "squareNumbers = ", squareNumbers, " squareNumbers[-1] = ", squareNumbers[-1]
            if (i % squareNumbers[-1]) == 0:
                #print "1 i = ", i, " squareNumbers[-1] = ", squareNumbers[-1], " i % squareNumbers[-1] = ", i % squareNumbers[-1]
                dpMatrix[i] = (i/squareNumbers[-1])
    
            else:
                #maximum is i
                n0 = i
                n4 = []
                for sq in squareNumbers[::-1]:
                    #print "sq = ", sq
    
                    if sq > 0 and i % sq == 0:
                        n0 = i / sq
                        break
    
                    else:
                        div1 = i / sq
                        rem1 = i % sq
    
                        n4.append(div1+dpMatrix[rem1])
    
    
                #print "n0 = ", n0, "n4 = ", n4
    
                minN4 = min(n4)
    
                #print "2 i = ", i
                n1 = dpMatrix[i-1] + 1
                #print "n1 = ", n1
    
                b1 = i / squareNumbers[-1]
                remaining = i % squareNumbers[-1]
    
                n2 = dpMatrix[remaining] + b1
    
                #print "b1 = ", b1, " remining = ", remaining, " dpMatrix[remaining] = ", dpMatrix[remaining], " n2 = ", n2
    
                dpMatrix[i] = min(n0, n1, n2, minN4)
                #print "2 dpMatrix = ", dpMatrix
        #print "in the end, dpMatrix = ", dpMatrix
    
        return dpMatrix[-1]

Log in to reply
 

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