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

Question

我了解到动态规划（DP）有两种：自上而下和自下而上。

在自顶向下中，您使用递归和记忆。在自下而上中，您只需填充一个数组（一个表）。

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

Answer 1

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