I made these two lists static however still TLE
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ self.dp = [i for i in range(n+1)] self.squares = [i*i for i in range(1, int(n**0.5) + 1)] for i in range(1, n+1): for sq in self.squares: if i - sq < 0: break self.dp[i] = min(self.dp[i], self.dp[i - sq] + 1) return self.dp[-1]
I tried with DP algorithm but get very poor performance (5%), the same algorithm beats 99% in "Ugly Number II" which is a quite similar problem.
My code is about twice speed as yours, but stil TLE, sigh
def numSquares(self, n): """ :type n: int :rtype: int """ if math.sqrt(n) == int(math.sqrt(n)): return 1 l = map(lambda i : i*i, [i for i in range(1, int(math.sqrt(n)))]) f = [ 0 for i in range(n+1) ] i = 1 while i < n+1: f[i] = min([ f[i-j] for j in l if i - j >= 0 ]) + 1 i += 1 return f[n]
Because Python is slow, which forces you to find a better algorithm. Or, you can use other languages to AC.
@zkh1991 I have the same question
@zkh1991 Replace the if statement by if i < sq
DP solution can be accepted, my code is 99% the same as your but only process a corner case at the very beginning , not very good performance but still beats 1/3 of the solutions on average:
if n == int(n**0.5): return 1 dp = [i for i in xrange(n+1)] square = [i**2 for i in xrange(int(n**0.5)+1)] for i in xrange(1,n+1): for item in square: if i-item<0: break else: dp[i] = min(dp[i],dp[i-item]+1) return dp[n]
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.