Can any one help me with the Bottom up approach in Dynamic programming as much as possible Illustrative manner? sources and links would also be appreciated .
bottom up approach is actually, a way to carry out DFS in a DAG that corresponds to the dynamic solution space of the problem. If you have thought of the top-down solution to the problem , with memoization and recursion (which is in some sense easier than coming up with bottom-up solution), you can apply the knowledge of the recurrence , to find a bottom-up solution , with correct implementation of the direction in which the DFS has to be performed in the corresponding DAG of the solution space.
Keep in mind, that your solution must not calculate a value a dependent value before calculating the values on which it depends( in other words keep the track of the direction in which the DAG is progressive or the topological ordering of the solution DAG).
1 Like