自下而上和自上而下有什么区别？

Question

自底向上方法（用于动态编程）包括首先查看“较小”的子问题，然后使用较小问题的解决方案解决较大的子问题。

在自上而下的在于解决“自然地”的问题，并检查是否已计算出前解决的子问题。

我有点困惑。两者有什么区别？

Answer 1

自上而下和自下而上的DP是解决相同问题的两种不同方法。考虑一种用于计算斐波那契数的记忆（自上而下）与动态（自底向上）编程解决方案。fib_cache = {}def memo_fib(n):&nbsp; global fib_cache&nbsp; if n == 0 or n == 1:&nbsp; &nbsp; &nbsp;return 1&nbsp; if n in fib_cache:&nbsp; &nbsp; &nbsp;return fib_cache[n]&nbsp; ret = memo_fib(n - 1) + memo_fib(n - 2)&nbsp; fib_cache[n] = ret&nbsp; return retdef dp_fib(n):&nbsp; &nbsp;partial_answers = [1, 1]&nbsp; &nbsp;while len(partial_answers) <= n:&nbsp; &nbsp; &nbsp;partial_answers.append(partial_answers[-1] + partial_answers[-2])&nbsp; &nbsp;return partial_answers[n]print memo_fib(5), dp_fib(5)我个人觉得记忆很自然。您可以采用递归函数并通过机械过程将其记忆化（首先在缓存中查找答案，并在可能的情况下返回它，否则以递归方式对其进行计算，然后在返回之前将计算结果保存在缓存中以备将来使用），而自下而上动态编程要求您对计算解决方案的顺序进行编码，这样在它依赖的较小问题之前就不会计算“大问题”。