动态编程-自上而下与自下而上 [英] Dynamic Programming - top-down vs bottom-up

问题描述

我了解到的是动态编程(DP)有两种:自顶向下和自底向上.

What I have learnt is that dynamic programming (DP) is of two kinds: top-down and bottom-up.

在自上而下中，您将递归与备忘录一起使用.在自下而上中，您只需填充一个数组(一个表).

In top-down, you use recursion along with memoization. In bottom-up, you just fill an array (a table).

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

Also, both these methods use same time complexity. Personally, I find top-down approach more easier and natural to follow. Is it true that a given question of DP can be solved using either of the approaches? Or will I ever face a problem which can only be solved by one of the two methods?

推荐答案

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

Well I believe theoretically you should be able to solve a DP problem with either approach. However, there are instances when bottom up approach can become too expensive. Consider a knapsack problem with the knapsack_size = 200,000 and the num_items = 2000. To fill in a two dimensional DP table with just ints is not going to be possible. You'll exhaust the main memory of an ordinary computer. Moreover, you do not require to fill in all the entries in a table to achieve the desired final computation. A recursive top-down approach is far superior in a case like this. Hope it helps.

这篇关于动态编程-自上而下与自下而上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！