Editing Dynamic programming (section)

=== Fibonacci sequence ===
Using dynamic programming in the calculation of the ''n''th member of the [[Fibonacci sequence]] improves its performance greatly. Here is a naïve implementation, based directly on the mathematical definition:

 '''function''' fib(n)
     '''if''' n <= 1 '''return''' n
     '''return''' fib(n − 1) + fib(n − 2)

Notice that if we call, say, <code>fib(5)</code>, we produce a call tree that calls the function on the same value many different times:

# <code>fib(5)</code>
# <code>fib(4) + fib(3)</code>
# <code>(fib(3) + fib(2)) + (fib(2) + fib(1))</code>
# <code>((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>
# <code>(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))</code>

In particular, <code>fib(2)</code> was calculated three times from scratch. In larger examples, many more values of <code>fib</code>, or ''subproblems'', are recalculated, leading to an exponential time algorithm.

Now, suppose we have a simple [[Associative array|map]] object, ''m'', which maps each value of <code>fib</code> that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only [[Big-O notation|O]](''n'') time instead of exponential time (but requires [[Big-O notation|O]](''n'') space):

 '''var''' m := '''''map'''''(0 → 0, 1 → 1)
 '''function''' fib(n)
     '''if ''key''''' n '''is not in ''map''''' m 
         m[n] := fib(n − 1) + fib(n − 2)
     '''return''' m[n]

This technique of saving values that have already been calculated is called ''[[memoization]]''; <!-- Yes, memoization, not memorization. Not a typo. --> this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.

In the '''bottom-up''' approach, we calculate the smaller values of <code>fib</code> first, then build larger values from them. This method also uses O(''n'') time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(''n'') space to store the map.

 '''function''' fib(n)
     '''if''' n = 0
         '''return''' 0
     '''else'''
         '''var''' previousFib := 0, currentFib := 1
         '''repeat''' n − 1 '''times''' ''// loop is skipped if n = 1''
             '''var''' newFib := previousFib + currentFib
             previousFib := currentFib
             currentFib  := newFib
         '''return''' currentFib

In both examples, we only calculate <code>fib(2)</code> one time, and then use it to calculate both <code>fib(4)</code> and <code>fib(3)</code>, instead of computing it every time either of them is evaluated.