def fib(n):
    '''Computes the nth Fibonacci number for nonnegative integer n
       by the naive method.'''
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

def memfib(m):
    '''Computes the mth Fibonacci number for nonnegative integer m
       by memoization.'''
    table = (m + 1) * [None]
    def f(n):
        if table[n] == None:
            if n <= 1:
                table[n] = n
            else:
                table[n] = f(n-1) + f(n-2)
        return table[n]
    return f(m)

def dpfib(n):
    '''Computes the nth Fibonacci number for nonnegative integer n
       using dynamic programming.'''
    table = [None] * (n+1)
    for i in range(n+1):
        if i == 0 or i == 1:
            table[i] = i
        else:
            table[i] = table[i-1] + table[i-2]
    return table[n]

def ben_fib(n):
    '''Computes the nth Fibonacci number for nonnegative integer n
       using constant amount of space.

       Author: Ben Weiner
    '''
    if n <= 1:
        return n
    else:
        current = 1
        previous = 0
        for i in range(2, n+1):
            current = current + previous
            previous = current - previous
        return current

def dmemfib(m):
    '''Computes the mth Fibonacci number for nonnegative integer m
       by memoization and using a dictionary as a table.'''
    table = {}
    def f(n):
        if n not in table:
            if n <= 1:
                table[n] = n
            else:
                table[n] = f(n-1) + f(n-2)
        return table[n]
    return f(m)

def ddpfib(n):
    '''Computes the nth Fibonacci number for nonnegative integer n
       using dynamic programming and using dictionary as a table.'''
    table = {}
    for i in range(n+1):
        if i == 0 or i == 1:
            table[i] = i
        else:
            table[i] = table[i-1] + table[i-2]
    return table[n]

for n in range(21):
    print '%d: %d %d %d %d %d %d' % (n, fib(n), memfib(n), dpfib(n), ben_fib(n),
                               dmemfib(n), ddpfib(n))