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

Question

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

在top-down中，您使用递归和记忆。在bottom-up中，您只需填充一个数组（表格）。

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

Answer 1

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

Answer 2

自下而上的 DP 要求您了解递归如何精确构建完整的解决方案，即创建了什么样的子问题，它们是如何被基本案例填充的，因此在自上而下编写自下而上的动态编程有点困难必须编写一个回溯解决方案（仍然很难想到），然后查看回溯解决方案的状态。states 表示递归函数的那些参数，这些参数在后续递归调用期间发生变化。

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

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