这是一个创建于 3125 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目来自： 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
Valyrian 2015-10-26 04:20:56 +08:00  1
这个优化是 memoization ，不是 DP
DP 是指一个 algorithm 运行一次时，会 reuse subproblem 的结果 memoization 是指一个 function 被 call 多次时， reuse 以前计算的结果 可以说 memoization 包括 DP 你的解法仅仅是 DP ，他的是 memoization http://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming |
 |
3
yujia 2015-10-26 05:37:14 +08:00
Memoization 是避免重复运算的必要手段，在 AI 里使用非常广的啊。
|
 |
4
binux 2015-10-26 06:41:32 +08:00
@20015jjw 我觉得不算是合法的，从 c 语言的函数入口看出，给出的方案应该是在函数这个基础上独立的，不应该依赖函数外部变量。
|
 |
5
jo32 2015-10-26 09:44:12 +08:00 via iPhone
我也感觉是作弊，对于某个 case ，算法复杂度的评定只与当前 case 有关才对。
|
 |
6
illuz 2015-10-26 10:23:12 +08:00 1
这就是 ACM 的「打表」，因为 ACM 的输入一般是多组一起输的，所以打表是 OK 的。
LeetCode 跑 test 时没有 new 个新的 Solution ，所以导致这种解也能过，不是很应该。 面试的时候得看面试官怎么看了，如果能做出正解当然是最好的了。 |
 |
9
virusdefender 2015-10-26 10:59:06 +08:00
不就是记忆化么，没问题吧
|
|
10
illuz 2015-10-26 12:40:42 +08:00 1
@20015jjw
你的思路是没错的，这样的算法复杂度是 O(n*sqrt(n)) 的，不过是 Python 比较不给力，容易 TLE 。我以为会是你这样算过去算了不少没用到的数据，写了个递归的版本，结果爆栈了。在 C++ 下，这递推和递归都是可以的，这复杂度是 OK 的。 用 static 应该也是种优化方法，毕竟这个问题的解存得下，而且用 Python 不好做。 其它的解法还有 BFS 和数学方法，可以看看 https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics 。 数学的解法也是惊艳呀。 |
 |
12
lzdhlsc 2015-10-26 16:03:52 +08:00
我试过 BFS 可以过的
|
Select Language