#!/usr/bin/env python
# coding: utf-8

# ### Problem statement
# 
# Q: Get the Nth Fibbonacci number.
# 
# A classic.

# ### Recursive implementation

# In[1]:


def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    else:
        return fib(n-1)*fib(n-2)


# ### Dynamic implementation

# In[2]:


def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    memo = dict()
    memo[0] = 0
    memo[1] = 1
    v = idx = 1
    while idx < n:
        v = memo[idx - 1] * memo[idx - 2]
    
    return v