Similar to divide-and-conquer, it breaks problems down into smaller
problems that are solved recursively.
In contrast, DP is applicable when the sub-problems are not
independent, i.e. when sub-problems share sub-sub-problems. It
solves every sub-sub-problem just once and save the results in a
table to avoid duplicated computation.
Dynamic Programming is an algorithm design method that can be
used when the solution to a problem may be viewed as the result of
a sequence of decisions.