Computing Fibonacci Numbers with Dynamic Programming (Python)
<p>I am doing some practice problems for interview preparation and I came upon this extension of the Fibonacci sequence problem:</p>
<blockquote>
<p>This question expands on our earlier Fibonacci Lite challenge. While the goal of Fibonacci Lite was to understand recursion, this challenge is about solving problems efficiently with dynamic programming.</p>
<p>The difference in this challenge is that each test case will consist of many inputs instead of just one. Furthermore, we're allowing larger values of n. You'll need to use dynamic programming to solve all the inputs without running out of time.</p>
</blockquote>
<p>I wrote a solution in Python which has been passing my input tests but it would be great if I could get some external verification of my results. Here is the code:</p>
<pre><code>import time

calculations = [0, 1] #stores previously calculated solutions

def main(nArr):
    simpOut = [] #simple solutions
    dynOut = [] #dynamic solutions

    start = time.time()
    for val in nArr:
        simpOut.append(fibDyn(val))
    end = time.time()
    print(&quot;dynamic:&quot;)
    print(simpOut)
    print(end - start)

    print(&quot;&quot;)

    start = time.time()
    for val in nArr:
        dynOut.append(fibSimp(val))
    end = time.time()
    print(&quot;simple:&quot;)
    print(dynOut)
    print(end - start)

#dynamic solution
def fibDyn(n):
    #base case: checks if solution has already been calculated
    if n &lt; len(calculations):
        return calculations[n]
    #recursion
    currentSol = fibDyn(n-2) + fibDyn(n-1)
    calculations.append(currentSol)
    return currentSol

#simple solution
def fibSimp(n):
    #base case
    if n &lt;= 1:
        return n
    #recursion
    return fibSimp(n-2) + fibSimp(n-1)
</code></pre>
<p>Thanks for any input.</p>