Dynamic Programming – Intro
I’ll confess – I always had (or maybe still have) issues solving dynamic programming (DP) questions. I mean, it’s just complicated, not as straightforward to understand. And how do we even know that a given question can be solved using dynamic programming?
There are two things to look for in order to understand if a given problem can be solved using dynamic programming.
Are there “overlapping sub-problems”?
Is there a defined structure or a “optimal sub-structure”?
If the above two conditions hold true for any given problem, it can usually be solved using dynamic programming. In this post, I will talk about overlapping sub-problems and the two common approaches to solve such problems. In the next post, I will talk about what is an optimal sub-structure.
Think of how a fibonacci series is calculated using recursion. Let’s take the example of fib(5). In calculating fib(5), we end up calculating fib(3), fib(2), fib(1) more than 1 time. If we were to calculate the fibonacci series of a much bigger number, there would be a lot of redundant calculations. If there was a way to calculate things only once and look them up as needed (look-up of O(1)), we would save a lot of time!
There are two ways to calculate things only once – a) Have a look-up table and build this look-up table on-demand, also called Memoization or top-down approach; or b) Have a look-up table and build this completely before hand, also called Tabulation or bottom-up approach.
HERE is some code that calculates the fibonacci series using recursion, memoization, and tabulation.
The figure below shows the time taken to calculate the same fibonacci number 45 using recursion, memoization, and tabulation. It took 11.32 seconds using recursion whereas only 1.71 seconds and 1.43 seconds using memoization and tabulation respectively. Indeed a great performance improvement!
Fig. 1. Time taken to calculate fib(45) using 3 different approaches
References:
GeeksforGeeks 2017. “Dynamic Programming | Set 1 (Overlapping Subproblems Property)”. https://www.geeksforgeeks.org/dynamic-programming-set-1/. [Online; accessed 14-Jan-2018].
RedHat 2017. “PERSISTENT NAMING”. https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/7/html/storage_administration_guide/persistent_naming. [Online;accessed 22-Nov-2017].