Start of Dynamic Programming | Recursion | Memoization

Book a Session

Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.

1] Recursion

function fib(n){
    if (n <= 1)
      return n; 
     return fib(n - 1) + fib(n - 2);
}

Recursion tree for execution of fib(5)

                         fib(5)
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

We can see that the function fib(3) is being called 2 times. If we would have stored the value of fib(3), then instead of computing it again, we could have reused the old stored value.

2] To store the values so that these values can be reused:
Memoization (Top Down): The memoized program for a problem is similar to the recursive version with a small modification that looks into a lookup table before computing solutions.

function fib(n) {
  let lookup = new Array(MAX);
  for (let i = 0; i < MAX; i++)
    lookup[i] = NIL;
  if (lookup[n] == NIL){
    if (n <= 1)
       lookup[n] = n;
    else
       lookup[n] = fib(n-1) + fib(n-2);
 }
 return lookup[n];
}

Ref- https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Keep learning, keep growing! —

Let’s connect on LinkedIn!. Please read more for more data structure javascript question. — Book a Session

I am listing the coding interview rounds for Big companies, which are very popular. If you are preparing for an interview or wanted to be in good company, please do check the below questions on Arrays, String and Linked List. I will come up with more interview coding round questions.

• Longest SubString Without Repeating Characters
• Valid Parentheses
• Rotate Array
• Move Zeros
• Linked List | Add Two Number

Follow me for more coding interview.