Leetcode 上 DP 的解法正确性

[20015jjw]

题目来自： 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 里是否可行？感觉这是赖皮的...

[Valyrian]

这个优化是 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

[20015jjw]

@Valyrian 嗷嗷嗷 所以这也是合法的咯

[yujia]

Memoization 是避免重复运算的必要手段，在 AI 里使用非常广的啊。

[binux]

@20015jjw 我觉得不算是合法的，从 c 语言的函数入口看出，给出的方案应该是在函数这个基础上独立的，不应该依赖函数外部变量。

[jo32]

我也感觉是作弊，对于某个 case ，算法复杂度的评定只与当前 case 有关才对。

[illuz]

这就是 ACM 的「打表」，因为 ACM 的输入一般是多组一起输的，所以打表是 OK 的。
LeetCode 跑 test 时没有 new 个新的 Solution ，所以导致这种解也能过，不是很应该。
面试的时候得看面试官怎么看了，如果能做出正解当然是最好的了。

[withlqs]

@Valyrian 其实记忆化和 dp 本质上是相同的。可顺序化的记忆化可以写成 dp

[20015jjw]

@illuz 正确解是 BFS ？

[virusdefender]

不就是记忆化么，没问题吧

[illuz]

@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 。
数学的解法也是惊艳呀。

[20015jjw]

@illuz ok 我来用 BFS 写写看 thx 数学办法太 6 明天面试肯定想不出...

[lzdhlsc]

我试过 BFS 可以过的