题目来自: 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 可以过的
|