题目来自： https://leetcode.com/problems/perfect-squares/
这是我的答案：
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
result = [0]
if len(result) <= n:
square = [s**2 for s in xrange(1, int(math.sqrt(n))+1)]
for i in xrange(len(result), n+1):
best = min(1 + result[i-sqr] for sqr in square if sqr <= i)
result.append(best)
return result[n]
运行超时
这是抄来的答案：
class Solution(object):
result = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if len(self.result) <= n:
square = [s**2 for s in xrange(1, int(math.sqrt(n))+1)]
for i in xrange(len(self.result), n+1):
best = min(1 + self.result[i-sqr] for sqr in square if sqr <= i)
self.result.append(best)
return self.result[n]
160ms...
我仔细想了一下，因为这道题的 test 有 600 个之多，而且一般都是递增的，这个答案的办法因为把 DP 的缓存放在了那个 solution object 里面，所以后面的 test 可以 reuse 那个 array 。不知道这个办法在 interview 里是否可行？感觉这是赖皮的...
1
Select Language