Dynamic Programming - top-down vs bottom-up

Question

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).

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?

Answer 1

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.