A gentle intro to dynamic programming!

Fib.py

class Solution_recursive:
    """
    Runtime: O(2^n)
    Spacetime: O(1)
    
    The classic approach to solving the Fibonacci sequence. The code is elegant but its runtime isn't 
    very pretty. Its  recursive nature necessitates that we calculate some values of f(n) multiple times.
    Consider this call graph where duplicated calls are denoted with `~`:
    
                        fib(7)
              ____________|__________
             |                       |
           fib(5)                  fib(6)
        _____|_______        ________|________
        |            |       |               |
    fib(3)        fib(4)   ~fib(4)         ~fib(5)
        |            |       |               |
continue...     continue... continue...    continue...
   
   (( even more duplicate calls as we continue))
   
   The right half of the call graph is a duplicate of the left half after a certain point. 
   How can we use this knowledge to improve our algorithm? 
    """
    def fib(self, n):
        if n <= 1: 
            return n
        
        return self.fib(n - 1) + self.fib(n - 2)


class Solution_simple_dynamic_programming_with_cache:
    """
    Runtime: O(n)
    Spacetime: O(n)
    
    Let's improve the algorithm by caching the left half calls so we don't need to repeat 
    them on the right half. By adding a cache we've made a tradeoff to improve our runtime 
    at the expense of our spacetime complexity. This approach systemically improves on the 
    recursive approach by caching the intermediate results so they are not calculated more than once. 
    
    Consider this call graph where duplicated calls are denoted with `~`:
    
                        fib(7)
              ____________|__________
             |                       |
           fib(5)                  fib(6)
        _____|_______        ________|________
        |            |       |               |
    fib(3)        fib(4)    cache[4]      cache[5]
        |            |                     
continue...     continue... 
   
   (( we dont continue the right hand side of the tree because its value is in the cache! ))
        
    
    """
    cache = {}
    
    def fib(self, n):
        if n <= 1: 
            return n
        
        if n not in self.cache: 
            self.cache[n] =  self.fib(n - 1) + self.fib(n - 2)

        return self.cache[n]

class Solution:
    """
    Runtime: O(n)
    Spacetime: O(1)
    
    We can still improve this algorithm further. We like our new runtime of O(n), but we're less 
    happy that we're no longer running in constant space. Do we need all of the values stored in our
    cache to calculate f(n)? When do we have cache hits? 
    
    This is a bottom-up approach that allows us to restrict our cache size to 2 variables giving
    us an algorithm that runs in constant space. By going bottom-up, we're able to build the 
    cache incrementally. In the previous soltuion, we only had cache hits for each value twice. Once
    when f(n - 2) equaled our stored value in the cache, and on the next iteration when it happened 
    again with f(n - 1). These cached values were never read from again. This means that we can
    `prune` our cache and keep only the values we need: f(n - 2) and f(n - 1).
    
    
    This is a good process for working through dynamic programming solutions.
        - First identify repeatable subproblems, i.e. the recursive approach
        - Next cache intermediate values.
        - Finally, prune the cache if you're able. 
    
    -- submission stats -- 
    Runtime: 12 ms, faster than 91.53% of Python online submissions for Fibonacci Number.
    Memory Usage: 11.8 MB, less than 50.00% of Python online submissions for Fibonacci Number.
    """
    def fib(self, n):
        if n <= 1:
            return n
        
        fib_minus_1 = 1
        fib_minus_2 = 0
        
        for _ in range(1, n):
            num = fib_minus_1 + fib_minus_2
            fib_minus_2, fib_minus_1 = fib_minus_1, num

        return num