5 lines Python static DP ( 160ms )

  • 3
    class Solution(object):
        numSquaresDP = [0]
        def numSquares(self, n):
            if len(self.numSquaresDP) <= n:
                perfectSqr = [v**2 for v in xrange(1, int(math.sqrt(n)) + 1)]
                for i in xrange(len(self.numSquaresDP), n + 1):
                    self.numSquaresDP.append( min(1 + self.numSquaresDP[i - sqr] for sqr in perfectSqr if sqr <= i))
            return self.numSquaresDP[n]

  • 2

    My solution with the exact same answer other than the DP array(numSquareDP) being inside the function exceeds the time limit, which is understandable as you are reusing the DP array for all the tests, which can improve the runtime significantly if there are many test, which there are, all 600 of them. Therefore, I'm not sure it this approach is valid.

Log in to reply

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