1. Introduction• DP is an optimization technique using caching.– If you have something you can cache, then you can use DP.• DP means nothing, it's completely garbage buzzword!• DP is a way to solve problems by breaking it down into a collection of sub-problems, solving each of those just once, and storing their solution in case next time the same sub-problem occurs.2. Memoization• Caching is a way to store values so you can use them later on.– Ideally, you can think of caching as a backpack that you take to school. Instead of going all the way home when you need something, you keep them around in your backpack.• Caching is just a way for us to speed up our programs and hold some piece of data in an easily accessible box.• Memoization is a specific form of caching that involves caching the return value.– If the input parameters of the function do not change, then it's memoized (because it uses the cached value).
functionaddTo80(n){return n +80;}let cache ={};functionmemoizedAddTo80(n){if(n in cache){return cache[n];}else{// this is a simple example but memoization is important when this operation takes a long time to run. cache[n]= n +80;return cache[n];}}
• There's an improvement we can make to the code above → Ideally, we don't want to fill the cache in the global scope (i.e. living outside the function).– Ideally, it's good practice to have memory (or cache) to live inside the function not polluting the global scope.• To do so, in JS, we can use closures.
functionmemoizedAddTo80(){let cache ={};returnfunction(n){if(n in cache){return cache[n];}else{ cache[n]= n +80;return cache[n];}}}const memoized =memoizedAddTo80();console.log(memoized(5));
• Note: DP allows us to use memoization to optimize our code.3. Fibonacci and DP• Here's the Fibonacci sequence → 0,1,1,2,3,5,8,13,21,34,55,89,144,233,...• With recursion, we are able to calculate the sequence
• How efficient is the above function?– It's not very efficient. It's time complexity → O(2n)– Also, with recursion we're adding every nested function call to the stack which increases space complexity.– With DP, we can do O(n) with this function.4. Dynamic Programming• This is what our previous Fibonacci function was doing based on recursion only:
Figure 1:Fibonacci with recursion
• As you can see, there are so many redundant calculations → For example, it's calculating fib(1) five times in order to get the fib(5) → This is super inefficient.• With DP, we only calculate each (repeating function) once, and whenever we need it, we just get the memoized value.• You can think of dynamic programming as: DP = Divide & Conquer + Memoization4.1. Steps to determine if a problem can be optimized by DP• It can be divided into sub-problems.• Recursive solution.• Are there repetitive sub-problems?• Memoize sub-problems?
