# 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. like`Fibonacci 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.

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.

Both `tabulated`

and `Memoized`

store the solutions of subproblems.

For example, memoized solution of `LCS`

problem doesn’t necessarily fill all entries.