动态规划 - 自上而下与自下而上

Question

我学到的是动态规划（DP）有两种：自上而下和自下而上。

在自上而下中，您将递归与记忆一起使用。在自下而上中，您只需填充一个数组（表格）。

此外，这两种方法使用相同的时间复杂度。就个人而言，我发现自上而下的方法更容易和自然地遵循。DP的给定问题真的可以使用其中任何一种方法来解决吗？还是我会遇到只能通过两种方法之一解决的问题？

Answer 1

好吧，

我相信从理论上讲，您应该能够用任何一种方法解决DP问题。但是，在某些情况下，自下而上的方法可能会变得过于昂贵。考虑knapsack_size = 200,000和num_items = 2000的背包问题。仅用ints填充二维DP表是不可能的。您将耗尽普通计算机的主内存。此外，您不需要填写表中的所有条目即可实现所需的最终计算。在这种情况下，递归自上而下的方法要优越得多。希望对您有所帮助。

Answer 2

自

下而上的 DP 要求您查看递归如何精确地构建完整的解决方案，即正在创建什么样的子问题，它们是如何由基本情况填充的，因此编写自下而上的动态编程有些困难，而自上而下必须编写回溯解决方案（这仍然很难想到），然后查看回溯解决方案的状态。在后续递归调用期间。

现在来谈谈时间的复杂性：
自下而上的 DP 比自上而下的 DP 更快，因为它不涉及任何函数调用。它完全取决于表条目，而在自上而下的 DP 中，它需要函数调用，从而导致隐式堆栈形成。

PS：要查看自上而下和自下而上的时间复杂度之间的差异，您需要解决 SPOJ 上的分配问题。

Answer 3

在解决动态问题时，您可能会考虑两件事......

在
1. 自下而上中，您必须在进入下一个上层之前填充整个级别。但在自上而下的情况下，如果不需要，可以跳过整个子树。这样自上而下可以节省很多额外的计算。因此，为了获得最佳时间，

if all sub-problems need not to be solved
    top-down
else
    bottom-up

2. 在空间需求方面，自下而上有一个优势。因为与递归自上而下的方法相比，它节省了大量的堆栈空间。因此，为了获得最佳空间，

bottom-up

但是，如果你觉得递归不是太深，但很宽，并且可以通过制表导致很多不必要的计算，那么你可以采用自上而下的方法进行记忆。