fib.py

class Solution:
    def fibTopDownMemo(self, n, memo):
        """
        [0,1,1,2,3,5,8]
        """

        if n in memo:
            return memo[n] # does the solution exist? if yes return it to prevent additional repeated calculation

        if n == 0 or n == 1:
            return n

        result = self.fibTopDownMemo(n - 1, memo) + self.fibTopDownMemo(n - 2, memo)
        memo[n] = result # store solution in memo

        return result

    def fibBottomUpTabulation(self, n):
        if n == 0 or n == 1:
            return n

        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n + 1):
           dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]



if __name__ == "__main__":
    solution = Solution()

    result = solution.fibTopDownMemo(6, {})
    assert result == 8
    print(result)
    print("Top Down Memoization - Test Cased Passed!")
    print()

    result = solution.fibBottomUpTabulation(6)
    assert result == 8
    print(result)
    print("Bottom Up Tabulation - Test Cased Passed!")