Leetcode 动态规划超时如何解决？

Question

在leetcode刷动态规划时发现问题，每次使用topdown 方法的时候都会通过一半测试用例，然后就显示超出时间限制。比如说爬楼梯：

class Solution:
    
    def climbStairs(self, n: int) -> int:
        memo = [0]*(n+1)
        print(memo)
        return self.numberOfWays(memo,n)
        
    def numberOfWays(self,memo,m):
        #how many ways can climb from 1 to m stairs
        #base
        if m == 1: 
            memo[m] = 1 
            return memo[m]
        if m == 2: 
            memo[m] = 2 
            return memo[m]
        #recursive
        else:
            memo[m] = self.numberOfWays(memo,m-1) + self.numberOfWays(memo,m-2)
            return memo[m]

这样写的话，在第38个测试用例中就会超时。但如果改成bottom-up:

class Solution:
    
    def climbStairs(self, n: int) -> int:
        memo = {}
        memo[1] = 1
        memo[2] = 2
        for i in range(3,n+1):
            memo[i] = memo[i-1] + memo[i-2]
        return memo[n]

就没有问题，非常快就可以出结果。

但在上课的时候说top-down和bottom-up都是对的，而且时间复杂度也不会差很多（一般来讲），但为什么在leetcode上频繁出现这种情况？而且看题解里面也都是用的bottom-up，加之我个人比较擅长top-down的思路……所以想知道是不是bottom-up实践上来说就是比top-down快，而且leetcode只能接受bottom-up的方法？

Answer 1

这两者时间还是差挺多的，动态规划的核心是避免重复计算子问题，你所写的top-down在递归的时候子问题还是重复算的，而buttom-up就没有重复计算，显然bottom-up更快。另外同样O(n)复杂度的话也可以差别很大，例如是n还是100n