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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.