Overlapping Subproblems
Divide and Conquer
Useful
when solutions of same subproblems are needed again and again, Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. likeFibonacci Numbers
Not useful
when there are no common (overlapping) subproblems because there is no point storing the solutions if they are not needed again. For example,Binary Search
doesn’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 Fibonacci
:
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.
1 |
|
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.
1 |
|
While in tabulated version, starting from the first entry, all entries are filled one by one.
Both tabulated
and Memoized
store the solutions of subproblems.
For example, memoized solution of LCS
problem doesn’t necessarily fill all entries.
Overlapping Subproblems
https://rug.al/2014/2014-09-24-overlapping-subproblems/