Dynamic Programming: top down versus bottom up comparison

5
votes

Can you point me to some dynamic programming problem statements where bottom up is more beneficial than top down? (i.e. simple DP works more naturally but memoization would be harder to implement?)

I find recursion with memoization much easier, and want to solve problems where bottom up is a better/perhaps only feasible approach.

I understand that theoretically both are equivalent, so even something like ease of implementation would count as a benefit.

2
dynamic-programming
You could look at the Knapsack problem. Making a table makes a lot of sense to solve it. Look at the slide labeled 12: es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf – wrhall

2 Answers

6
votes

You will apply bottom up with memoization OR top down recursion with memoization depending on the problem at hand .

For example, if you have to find the minimum weight independent path of a path graph, you will use the bottom up approach as you have to solve all the subproblems that are possible.

But if you have to solve the knapsack problem , you may want to use recursive top down with memoization as you have to solve a limited number of subproblems. Approaching the knapsack problem bottom up will cause the algo to solve a lot of redundant problems that are not used in the original subproblem.

3
votes

Two things to consider when deciding which algorithm to use

  1. Time Complexity. Both approaches have the same time complexity in general, but because for loop is cheaper than recursive function calls, bottom-up can be faster if measured in machine time.
  2. Space Complexity. (without considering extra call stack allocations during top-down) Usually both approaches need to build a table for all sub-solutions, but bottom-up is following a topological order, its cost of auxiliary space can be sometimes reduced to the size of problem's immediate dependencies. For example: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), we only need to store the past two calculations

That being said, bottom-up is not always the best choice, I will try to illustrate with examples:

  1. (mentioned by @Nikunj Banka) top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems. A silly example would be 0-1 knapsack with 1 item...run time difference is O(1) vs O(weight)
  2. you might need to perform extra work to get topological order for bottm-up. In Longest Increasing Path in Matrix, if we want to do sub-problems after their dependencies, we would have to sort all entries of the matrix in descending order, that's extra nmlog(nm) pre-processing time before DP