V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
20015jjw
V2EX  ›  问与答

Leetcode 上 DP 的解法正确性

  •  
  •   20015jjw · 2015-10-26 02:40:40 +08:00 · 2719 次点击
    这是一个创建于 3307 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    12 条回复    2015-10-26 16:03:52 +08:00
    Valyrian
        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
    20015jjw
        2
    20015jjw  
    OP
       2015-10-26 04:42:43 +08:00
    @Valyrian 嗷嗷嗷 所以这也是合法的咯
    yujia
        3
    yujia  
       2015-10-26 05:37:14 +08:00
    Memoization 是避免重复运算的必要手段,在 AI 里使用非常广的啊。
    binux
        4
    binux  
       2015-10-26 06:41:32 +08:00
    @20015jjw 我觉得不算是合法的,从 c 语言的函数入口看出,给出的方案应该是在函数这个基础上独立的,不应该依赖函数外部变量。
    jo32
        5
    jo32  
       2015-10-26 09:44:12 +08:00 via iPhone
    我也感觉是作弊,对于某个 case ,算法复杂度的评定只与当前 case 有关才对。
    illuz
        6
    illuz  
       2015-10-26 10:23:12 +08:00   ❤️ 1
    这就是 ACM 的「打表」,因为 ACM 的输入一般是多组一起输的,所以打表是 OK 的。
    LeetCode 跑 test 时没有 new 个新的 Solution ,所以导致这种解也能过,不是很应该。
    面试的时候得看面试官怎么看了,如果能做出正解当然是最好的了。
    withlqs
        7
    withlqs  
       2015-10-26 10:32:40 +08:00
    @Valyrian 其实记忆化和 dp 本质上是相同的。可顺序化的记忆化可以写成 dp
    20015jjw
        8
    20015jjw  
    OP
       2015-10-26 10:48:01 +08:00
    @illuz 正确解是 BFS ?
    virusdefender
        9
    virusdefender  
       2015-10-26 10:59:06 +08:00
    不就是记忆化么,没问题吧
    illuz
        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
    数学的解法也是惊艳呀。
    20015jjw
        11
    20015jjw  
    OP
       2015-10-26 13:09:06 +08:00
    @illuz ok 我来用 BFS 写写看 thx 数学办法太 6 明天面试肯定想不出...
    lzdhlsc
        12
    lzdhlsc  
       2015-10-26 16:03:52 +08:00
    我试过 BFS 可以过的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5847 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 02:52 · PVG 10:52 · LAX 18:52 · JFK 21:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.