Divide and Conquer
Usefulwhen solutions of same subproblems are needed again and again, Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. like
Not usefulwhen there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again. For example,
Binary Searchdoesn’t have common subproblems
There are two ways to store values so that these values can be reused and I will also show two instances of dynamic programming by
Memoization (Top Down)
try to touch from top to bottom, calculate and store value whenever this value is not found in our, otherwise just use it.
In Memoized version, table is filled on demand, unlike the tabulated version, all entries of the lookup table are not necessarily filled in memoized version.
Tabulation (Bottom Up)
try to touch from bottom to top, calculate, calculate and store value.
While in tabulated version, starting from the first entry, all entries are filled one by one.
Memoized store the solutions of subproblems.
For example, memoized solution of
LCS problem doesn’t necessarily fill all entries.
24 September 2014