class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ # invalid input: if n < 1: return 0 # valid input: # dp: dp = range(n+1) num = 2 while num <= n: count = 5 i = 1 while num - i ** 2 >= 0: count = min(count, dp[num - i**2] + 1) i += 1 dp[num] = count num += 1 return dp[-1]
python runs much slower than c/c++
same algorithm, cpp code can AC while python code got TLE
so sad about that .....
I think for python we just have to find a better algorithm!
I was facing the same problem. I tried to make the dp global. So every time the function is called I am not building the dp. I am using the dp from the previous testcases. It doesn't change the worst case time-complexity but your solution would get accepted.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.