Dynamic Programming

Dynamic Programming is a technic for optimizing algorithms that end up solving multiple times the same thing;

It is about remembering partial results.

There are two methods: top-to-bottom “Memoization” and bottom-to-top “Tabulation”.

Memoization

The recursion issue is you might end up making the same call (same arguments) and doing the same actual work. Look at the previous picture in this article, how many times F(2), F(1), and F(0) are called.

Memoization (or memoisation and not memorization) is an optimization that makes you store the results previously obtained to avoid new calls. Instead of reprocessing, again and again, the same results, we return the cached partial results.

As you can see, all calls with the same parameters are executed only once, reducing the time complexity to O(n), but we need O(n) space to store the partial results. It is a trade-off; we reduce time complexity by increasing space complexity.

Tabulation

Contrary to Memoization, Tabulation starts from the base case and can build up the partial results, which can be treated iteratively.

As you can see, we start with the two base cases (0 and 1), build up, and store all partial results until we reach “n.” As the Memoization, time and space complexity is O(n).

The one to choose

The main difference is that the Tabulation will compute all partial results up to the one we are looking for; on the contrary, the Memoization will only calculate the required partial results.

Then, if you need to compute all subproblems, go for Tabulation; otherwise, go for Memoization.

<< Recursion VS Iteration | Book | Two-Pointer vs Sliding window >>