How I'm learning the basics of Dynamic Programming!

b00000001 — Tue, 12 Apr 2022 00:38:34 +0000

Okay so I'm just at the start of my journey deep diving into dynamic programming. It turns out for me personally I needed to lean heavily on the visual aspect of dynamic programming for the concepts to really stick and even still I have trouble. To help me, I've leveraged the assistance of a tool for visualizing algorithms step by step. AlgoViz, is the site in question.

Now, what I want to go over briefly is the recursive Fibonacci algorithm.

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

When I input this Algorithm into AlgoViz, step by step we get the following, which I will attempt to explain for my understanding and yours!

1. fib(3) 
    * call function with integer 3 as an input

2. function declares n = 3

3. evaluate (n <= 2)
    * n is currently 3, which is not less than, or equal to 3

4. evaluate (n - 1)
    * n is 3, subtract 1 and n == 2

5. declare n = 2
    * now n has been reduced to 2 by previous evaluation 

6. evaluate (n <= 2)
    * n = 2, n is less than, or equal to 2

7. call fib(n - 1) 
    * n - 1 = 1
    n is now less than or equal to 2, this is base case
    now the recursive function will start to evaluate the -2 side of the return statement, at this point it will evaluate n at the value of 3 again.

8. evaluate (n - 2)
    * 3 - 2 = 1
    this is a base case

9. declare n = 1
    * function now receives 1 as input

10. evaluate (n <= 2) 
    * 1 is less than or equal to 2

11. call fib(n - 2) = 1
    * base case, no further work to be done

12. return 1 + 1 (return fib(n-1) + fib(n - 1))
    * the value that was left from evaluating the -1 side of the tree was 1, from step 7. The Value from evaluating the -2 side was also 1, from step 11. 1 + 1 = 2.

A crude tree for this would be:

           fib(3)  declaration (n = 3)                                     
              /      \
         -1  /        \   -2                                      
            /          \                                     
          (2)         (1) base                                   
         /              
        /                                
      (1) base

The return value is derived from adding the base cases. 1 + 1;
Here is how the tree would look with fib(4).

            fib(4)  declaration (n = 4)                                    
               /      \
         -1   /        \   -2
             /          \
            (3)         (1)
            / \                                 
           /   \                                   
          /     \                                
        (2)     (1)                                                          
         |
         |
        (1)

// 1+1+1 = 3

It was important for me to come to the understanding that the function evaluates the -1 (left) side of the tree first then moves on to the -2 side. You can see this once the base cases are hit at steps 7 and 11.

This does not touch on memoization or any more advanced concepts as I'm still learning those and felt that as a newbie, the visual aspects help quite a bit. If you're a newbie, I suggest also starting to learn Time/Space complexities and Asymptotic Analysis!

If this helped cheers, this is my first post, let me know if I missed anything or was just blatantly wrong. Feel free to link up with me on GH or LinkedIn!

DEV Community: b00000001

How I'm learning the basics of Dynamic Programming!