CODEWITHSUNDEEP
algorithmdynamic-programmingmemoization
NightFurry
NightFurry

Reputation: 358

Does there always exist a dynamic programming bottom up solution for corresponding memoization method

I searched some existing text like Dynamic programming and memoization

But Still I could not conclude my doubt.

Memoization is very easy to look and implement. But corresponding DP solution takes much brain. Sometimes, I'm unable to find solution through DP paradigm.

I want to know If a problem has solution through memorization(top down approach), Is it enforces there exist a DP bottom up solution?

Upvotes: 3

Views: 1322

Answers (2)

Gassa
Gassa

Reputation: 8846

In a way, yes, but the details may be cumbersome.

The main difference between bottom-up and top-down approaches is that we know the order to traverse the state space in advance.

If you are exploring a graph with a depth-first search (which is what memoization essentially does), there exists an order in which the vertices of that graph finish being processed (a value for the vertex is calculated and memoized). This order can be found by topologically sorting the graph. Then, you can calculate the values in that order, which can be viewed as going bottom up.

Still, for some graphs, there is no topological order coherent with the graph and expressible in a simple way (like for (row) for (col) calc (row, col)).

Another problem with going bottom up is that, with a top-down solution, we visit only the states we in fact need for the calculation, and their amount may be way less than the total amount of states.

Addition. Moreover, for some algorithms, the order is calculated on-the-fly based on the values we calculate. For a simple example, Dijkstra's algorithm can be viewed as dynamic programming, but the order in which the vertices are added to the tree of shortest paths depends on the distances we calculate. Thus we have to find all shortest distances, one way or another, to find the order, and so any bottom-up solution after finding the order becomes unnecessary.

Upvotes: 3

Nikunj Banka
Nikunj Banka

Reputation: 11365

Yes, every dynamic programming problem that has a top-down solution also has a corresponding bottom up dynamic programming solution.

You can prove this by visualizing any DP problem's state space as a DAG with the nodes representing the states and the edges representing the dependency between nodes. For eg, if there is an edge from A to B in the DAG, then it means that to get a solution for state A, we must solve state B first.

Hence, solving the problem bottom up is equivalent to applying dynamic programming on the vertices of the DAG in the reverse order of its topological sort.

Upvotes: 4

Related Questions