Data structures and Algos ep 1! Dynamic Programming, Recursion and Memoization.

Funny enough , I didn’t understand this when I learned about this months ago, but my friend taught me recursion, memoization and dynamic programming in this way, and i wanted to write it out. As always, I find that I definitely know that I understand something when I can talk about it.

What’s Dynamic Programming and why should I care/learn it?

According to my google foo skills, dynamic programming is defined as an optimization of breaking down a problem into smaller parts, and then you solve the smaller parts then remembering the solutions so you can use it again with recomputing them.

The unfortunate thing is, dynamic programming comes up in interviews, it came up as a question for my screening for an interview I had. Soo yeah. If you didn’t know I’m a coding bootcamp student right now, we covered recursion, but not really much about memoization and dynamic programming. Memoization is a technique that you can use to avoid repeated calculations on the same problems, it caches a return value of a function based on the parameters. Dynamic programming breaks down a problem into similar smaller problems, you can apply recursion and memoization to it, you don’t necessarily have to, but recursion, memoization and such usually go hand-in-hand (kinda) at least that’s what I got from it.

What is Recursion?

A couple of months ago, I was preparing for an interview with a company, and one of the concepts I had trouble understanding was Recursion. So what is Recursion? Recursion according to the wikipedia definition, is a method that calls a function within their own code. A fun way I like to think of it is Russian nesting dolls. Some problems that can be solved iteratively, can also be solved recursively.

A simple example demonstrating both recursion and solving something iteratively is the factorial problem. A factorial states a positive integer, n is donated by n! it is the product of all positive integers less than or equal to n.

So if I was to find the factorial of 5. It would go:

5 * 4 * 3 * 2 * 1

This would equal 120. How can I write this in code? Iteratively, you can write it like this.

function factorial(n){
  if(n === 1 || n === 0){
  return 1 
} for(let i = n - 1; i >= 1; i--){
 n *= i
} return n 
} factorial(n)

To translate this into english, it means if n is equal to 1 or 0, return 1. If not, then keep going through it until it hits 1 and multiply it. (Dunno if that makes sense) but looking at this, it looks kinda ugly. So how would this look with recursion?

const factorialize = (num) => {
 if(num === 1){
  return 1 
} else {
  return num * factorialize(num-1)
  }
}

This is pretty much the same thing as above. It looks a lot cleaner than the iterative version. So in recursion, there is always a base case which terminates the function. The base case here would be when our input is equal to 1. When you think about it, knowing that when you do a factorial its num * num — 1 until it goes down to 1. So when it hits 1 it stops.

If the number is greater than 1, it’ll go through the recursive case, until it triggers the base case.

Sounds simple right? But what happens when things get a little bit bigger? That’s where memoization comes in.

Another problem, applying recursion and memoization.

So a problem I like to use to explain recursion and this next concept is known as the Fibonacci Sequence. The fibonacci sequence states that each number is the sum of the two preceding ones, starting from 0 and 1.

The beginning of the sequence starts 0, 1, 1, 2 ,3,5,8. Knowing that the number are the sum of the two preceding ones we can imagine, okay recursion.

First we think about the base case. Thinking back to the factorial example, the base case is where the function terminates. Going back to the defintion of the fibonacci sequence it states that it starts with 0 and 1. This might be a good place to declare our base case. (From here on out I’ll be writing in ES6 arrow functions, because we’re classy and modern coders, fun fact my HS math teacher would say something like that back then lmaoo)

fibonacci = (n) => {
if(n <= 1){
 return n
}

Our base case states if the input of n is less than or equal to 1, we will return n. Going back to our definition, we know that in the fibonacci sequence the first two numbers are 0 and 1.

Now what about the recursive case?

Going back to the definition we know that the fibonacci sequence states okay you add the two numbers before it. So now we’re thinking recursion! Overall, the final equation of this recursively looks like this:

fibonacci = (n) => {
  if(n <= 1){
   return n 
} return fibonacci(n-1) + fibonacci(n-2)
}

Cool, we got our function now let’s try to run it in a terminal and see what happens. We’re going to do this:

console.log(fibonacci(10));
console.log(fibonacci(100));

When we run this in a terminal, if we console.log fibonacci(10) we’re going to get 55. However, if we run fibonacci(100) nothing happens. Does this mean our terminal is broken?

No its not!

The bigger the number is, the longer then run time! Think back to big O notation. So how do we solve this? We use a technique called memoization.

According to wikipedia, memoization is an optimization technique that is used to speed up computer programs by storing the results of function calls and returning the cached result.

So now you’re looking at this and going WTF?! What does that mean. In simple terms, memoization stores the parts of the function that has already been calculated and it won’t calculate it again.

So now knowing this, how would we write this function. We’re going to apply memoization in this function.

fibonacci= (n,memo) => {
memo = memo || {}
if(memo[n]){
  return memo[n]
}

Now you’re probably thinking…what is this, I don’t even?!

The first part of the function is what we’re going to use to store the numbers that have already been calculated. Thinking back at the definition of memoization, we are caching or saving a value that has already been calculated.

The if statement, we are going to be checking the cached value for n and we return a value if there is something there.

So the final function will look like this.

fibonacci = (n,memo) {
  memo = memo || {}
  if(memo[n]){
    return memo[n]
} if(n <= 1){
   return 1 
}  return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)

If we were to calculate now the fibonacci of 100, we would get 573147844013817200000, and pretty quickly too.

So how was this able to happen?

As mentioned memoization stores the previously calculated part of the function in cache, so it won’t calculate it again.

Dynamic Programming Leetcode problem: House robber!

So now that we’ve learned recursion and memoization let’s tackle a leetcode problem, where we may apply these two concepts.

This is leetcode problem 198. Which can be seen here: https://leetcode.com/problems/house-robber/

So looking at this problem we know a couple of things:
-if two adjacent house are broken into in the same night we fail.
-we need to determine the maximum amt we can get without messing up.
-the input of this problem is an array, so here is an example of how the solution would look like.
Example:
nums = [2,7,9,3,1]
The maximum amount would be 12, because:
2+9+1 = 12
and we can’t touch the adjacent houses otherwise…fail!

So how would we break this down?

Knowing the information we have above we can write our first part of the code, where we check through it.

let rob = (nums) => {
  if(nums == null || nums.length == 0) 
   return 0;
  if(nums.length === 1) 
   return nums[0]
  if(nums.length === 2)
   return Math.max(...nums)

So what’s happening here?
Thinking back at the example that was given to us we are trying to find the sum of the greatest amount we can get without going through adjacent numbers.
So if there is nothing in our array, we would return 0.
If there is only one value in our array, then that is what we’re going to have back. So example:

If nums = [7] then our maximum profit would equal 7.
If we have two values in our array then the maximum value would be the maximum amount.

So going past those cases, what do we do we do if we now have more than 2 numbers in our nums array?

let dp = [nums[0], Math.max(nums[0], nums[1])]

First we do something similar to what we’ve done in the first part of the function. We have to check which of the first two we have is the bigger one so $$$.

So since now we’re working with an array with more than two values we can loop through it, kinda like we’re looping through an array to find the sum. Except with this we also have to check and make sure we’re not adding the adjacent ones.

for(let i = 2; i < nums.length; i++){
  dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1])
}

So let’s break down what’s happening in this loop. We are checking through the second house, where the maximum profit will either be the current value + the profit of two numbers ago, since we’re doing alternate values, or we don’t go for it.

Lastly, we return the maximum amount from everything we just did!

return dp[dp.length — 1]

All in all, the final piece of code looks like this:

let rob = (nums) => {
  if(nums == null || nums.length == 0) 
   return 0 
  if(nums.length === 1) 
   return nums[0]
  if(nums.length === 2)
   return Math.max(...nums)
  let dp= [nums[0], Math.max(nums[0], nums[1])]
  for(let i = 2; i < nums.length; i++){
      dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1])
  }
  return dp[dp.length - 1]
}

This is one of many ways to solve leetcode problem 198! We can definitely see recursion be applied to this with the first part of the problem and then we see dynamic programming be applied to it.

Anyway, this is my first attempt blogging about a programming concept like this. This probably is not the best explanation, but I also wanted to see how much I understand this, and stuff. The next entry I hope to write will be about Linked Lists !

For the record, I don’t own the meme photos and the spongebob photo, I thought it would be something funny to add in.