import logging

steps = 0

def fibonacci_recursive(n):
    global steps
    steps += 1
    if n is 0:
        return 0
    elif n < 3:
        return 1
    else:
        return fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1)

def fibonacci_dp(n):
    global steps
    f0, f1 = 0, 1
    for i in xrange(1, n):
        steps += 1
        f0, f1 = f1, f0 + f1
    return f1

def fibonacci(n):
    """
    >>> fibonacci(1)
    1
    >>> fibonacci(2)
    1
    >>> fibonacci(3)
    2
    >>> fibonacci(4)
    3
    >>> fibonacci(5)
    5
    >>> fibonacci(6)
    8
    >>> fibonacci(20)
    6765
    """
    global steps
    steps = 0
    #ret = fibonacci_recursive(n)
    ret = fibonacci_dp(n)
    return ret

if __name__ == '__main__':
    import doctest
    logging.basicConfig(
        level=logging.INFO,
        format="%(message)s")
    doctest.testmod(verbose=False)

    logging.info("n\tfib\tsteps")
    for i in xrange(1, 31):
        ret = fibonacci(i)
        logging.info("%d\t%d\t%d" % (i, ret, steps))