Dynamic Programming combines solutions computed for sub-problems and stores them in the memory. Dynamic Programming mainly uses solutions to the same sub-problems repeatedly, and that’s the point. It makes sense to find a solution for each problem only once and reuse it later.

For example, unlike DP problems, the Merge Sort Algorithm also solves the subproblems like we do in DP but does not use these solutions multiple times.

In our Fibonacci problem, we solve the same problems multiple times. Why? Remember the formula for fib(n) = fib(n-1) + fib(n-2)? But for fib(n-1) we'll calculate the fib(n-2) and fib(n-3), and then calculate fib(n-2) again. Since we have no solution for fib(n-2) in memory, we'll repeat the same calculations multiple times. Here's why storing solved sub-problems in some tables makes sense.

Memoization

The memoized program is similar to the previous recursive solution but with additional space for storing values; let’s call it solved. When you solve some subproblem, put the solution to solved, and reuse it next time. The Memoization principle stores values from top to down, so it is also known as the Top-Down approach in Dynamic Programming.