关于记忆化搜索和动态规划在时间消耗上的问题

Question

老师好，我想问一下关于这一节第一个例题（leetcode 198） 的一个问题，您给出了基于记忆化搜索和动态规划的两种解法，这两种解法都是O(n^2) 的，但是不是在隐含的常数上会有区别，以至于记忆化搜索 总是比 动态规划 要慢一点呢（举个例子，记得您在前面讲斐波那契数列的时候讲过这两个一个是操作了2n次左右，一个是n次左右）

那么平常我碰到一个算法题，要是同时能用记忆化搜索和动态规划两种方法，是不是能用动态规划就更好一些呢，还是说得具体分析？如果说我现在要解决的不是一个数据规模较小的算法面试题，而是一个数据规模较大的实际问题，我也同时能使用这两个方法，那么选择哪个方法更好呢？

Answer 1

liuyubobobo 2021-03-14 21:02:29

不一定记忆化搜索一定比动态规划慢。需要具体问题具体分析。

这是因为使用动态规划，会把所有的状态遍历一遍，但是，在有的情况下，记忆化搜索可以跳过某些状态，只计算为了求得我们想要的结果，所需要的相应的状态。背包问题是一个典型的例子，如果物品的重量都很大的话，并不是所有的重量值都是可以通过物品组合得到的。

但是，如果不是这种情况，状态分布比较密的话，通常动态规划的性能会比记忆化搜索好，这是因为递归会产生性能消耗，但是这个消耗是常数级别的。

另外，有一些动态规划的优化方法，只能作用在动态规划的方法上。但是这类问题通常都是竞赛才需要考虑的。

整体，对于一个问题，如果你能直接想明白动态规划的写法，直接写动态规划，对于大多数面试问题是没有问题的；否则，我个人倾向于先实现一版记忆化搜索试试看。通常记忆化搜索的解法思维难度低一些。如果发现不符合性能要求，或者还需要优化，可以再改成动态规划。

继续加油！：）

• 提问者 皓哥卷起来 #1

  非常感谢！