5

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?

3 Answers 3

4

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.

2
  • 1
    "Moreover, you do not require to fill in all the entries in a table to achieve the desired final computation" --- it's not "moreover", it's the main point. Mar 30, 2015 at 17:20
  • When arrays are sparse in bottom-up DP, you can use hash table instead.
    – tejasvi88
    Jan 3, 2022 at 8:41
1

bottom-up DP requires you to see how the recursion was precisely building the complete solution i.e what kind of subproblems were being created how they were filled by the base cases hence it is somewhat difficult to write bottom-up dynamic programming while in top-down have to write a backtrack solution(which is still hard to think of) and then see the states of backtrack solution.states means those arguments to the recursive function that were varying during subsequent recursive calls.

Now coming to the time complexities:
Bottom-up DP is faster than top-down since it doesn't involve any function calls. It completely depends on the table entries while in top-down DP it requires function calls and thereby causing an implicit stack formation.

PS: to see difference between time complexities of top-down and bottom-up you need to solve ASSIGNMENTS problem on SPOJ.

1

When solving a dynamic problem you may consider two things...

  1. In bottom-up you have to fill an entire level before going to the next upper level. But in case of top-down an entire subtree can be skipped if not needed. In this way top-down can save a lot of extra calculations. So for optimal time,
if all sub-problems need not to be solved
    top-down
else
    bottom-up
  1. There is an advantage in bottom-up in terms of space requirement. Because it saves a lot of stack space as compared to recursive top-down approach. So for optimal space,
bottom-up

However, if you feel recursion is not too deep but is very wide and can lead to a lot of unnecessary calculation by tabulation, you can then go for top-down approach with memoization.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.