'''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))