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

Question

自底向上方法（用于动态编程）包括首先查看“较小”的子问题，然后使用较小问题的解决方案解决较大的子问题。在自上而下的在于解决“自然地”的问题，并检查是否已计算出前解决的子问题。我有点困惑。两者有什么区别？

Answer 1

自上而下和自下而上的DP是解决相同问题的两种不同方法。考虑一种用于计算斐波那契数的记忆（自上而下）与动态（自底向上）编程解决方案。

fib_cache = {}

def memo_fib(n):

  global fib_cache

  if n == 0 or n == 1:

     return 1

  if n in fib_cache:

     return fib_cache[n]

  ret = memo_fib(n - 1) + memo_fib(n - 2)

  fib_cache[n] = ret

  return ret

def dp_fib(n):

   partial_answers = [1, 1]

   while len(partial_answers) <= n:

     partial_answers.append(partial_answers[-1] + partial_answers[-2])

   return partial_answers[n]

print memo_fib(5), dp_fib(5)

我个人觉得记忆很自然。您可以采用递归函数并通过机械过程将其记忆化（首先在缓存中查找答案，并在可能的情况下返回它，否则以递归方式对其进行计算，然后在返回之前将计算结果保存在缓存中以备将来使用），而自下而上动态编程要求您对计算解决方案的顺序进行编码，这样在它依赖的较小问题之前就不会计算“大问题”。