'''The Fibonacci Sequence problem
with various solutions illustrating dynamic programming approaches.'''

def fib(n):
    '''Naive recursive solution:
    An important step!  It shows the logic of the problem.  In such a trivial
    case this is not a big deal, but in harder cases it is a worthwhile start!
    It is just not an efficient solution if many subproblems are
    reused many times.  Good first pass to test logic with *small* data!
    '''
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

def fibArbAccessTable(n): 
    '''Table with lookup when you need it ('memoizing' is the jargon) -
    no need to second guess the order of
    subproblems needed.  This is the user-level function with no reference
    to auxiliary data needed for the implementation.'''
    table = [-1]*(n+1)
    table[0] = 0
    table[1] = 1
    return _fibRec(n, table)

def _fibRec(i, table):  
    '''Recursive helping function for fibArbAceessTable,
    calculates the first time only, uses initialized auxiliary space.'''
    if table[i] >= 0:  # no calculation if already have the result
        return table[i]
    table[i] = _fibRec(i-1, table) + _fibRec(i-2, table) # calc, remember
    return table[i]

def fibTableTopo(n):
    '''In algorithm jargon:  We have figured out a topological order
    for the DAG of subproblem dependency.  We solve problems in that
    topological order, so we always have the previous results when needed.
    This avoids the recursive overhead of memoization.
    memoization is still useful if it is not clear ahead of time which
    subproblems will be needed, or if a significant number are not needed.
    '''
    table = [0]*max(2, n+1) # for simplicity so can always include base cases
    table[0] = 0
    table[1] = 1
    for i in range(2, n+1): # 2...n
        table[i] = table[i-1] + table[i-2]
    return table[n]

def fibTablePartNeeded(n):
    '''Besides having the topological order figured out, we see that beyond
    a certain point (two later here) we do not need remembered results,
    and we arrange to minimize memory used for past results.'''
    if n < 2:
         return n 
    last = 1
    prev = 0
    for i in range(2, n+1):
        val = last + prev
        prev = last
        last = val
    return val

def test(n):
    '''Check each version with input n.'''
    print("Results for", n)
    for f in [fib, fibArbAccessTable, fibTableTopo, fibTablePartNeeded]:
        print(f(n))