Fibonacci Numbers—Iterative Approach

Once we see how the array $F [\ ]$ is filled, we can replace the memoized recurrence with a simple for loop that intentionally fills the array in that order, instead of relying on a more complicated recursive algorithm to do it for us accidentally.

$\underline{IterFibo(n):} \\ \hspace{0.4cm} F[0]←0 \\ \hspace{0.4cm} F[1]←1 \\ \hspace{0.4cm} for\space i ← 2\space to\space n \\ \hspace{1cm} F[i] ← F[i − 1] + F[i − 2] \\ \hspace{0.4cm} return\space F[n]$

Explanation

• Line 7: The code declares a vector named F of size n+1 with initial value 0 for all elements.

• Lines 10–13: The code iterates from i=2 to i=n and calculates the Fibonacci number for each index i in the array F using the previously calculated values F[i-1] and F[i-2]. The calculated Fibonacci number for n is returned.

• Line 20: The code prints the 6th Fibonacci number to the console.

Now, the time analysis is immediate: $IterFibo$ clearly uses $O(n) additions$ and stores $O(n)$ integers.

This is our first explicit dynamic programming algorithm. The dynamic programming paradigm was formalized and popularized by Richard Bellman in the mid-1950s while working at the RAND Corporation, although he was far from the first to use the technique. In particular, this iterative algorithm for Fibonacci numbers was already proposed by $Virah\overset{-}{a}\underset{.}{n}ka$ and later Sanskrit prosodists in the 12th century, and again by Fibonacci at the turn of the 13th century!

Many years after the fact, Bellman claimed that he deliberately chose the name “dynamic programming” to hide the mathematical character of his work from his military bosses, who were actively hostile toward anything resembling mathematical research. The word “programming” doesn’t refer to writing code, but rather to the older sense of planning or scheduling, typically by filling in a table. For example, sports programs and theater programs are schedules of important events (with ads); television programming involves filling each available time slot with a show (and ads); degree programs are schedules of classes to be taken (with ads). The Air Force funded Bellman and others to develop methods for constructing training and logistics schedules, or as they called them, “programs.” The word “dynamic” was not only a reference to the multistage, time-varying processes that Bellman and his colleagues were attempting to optimize, but also a marketing buzzword that would resonate with the Futuristic Can-Do Zeitgeist of post-WWII America. Thanks in part to Bellman’s proselytizing, dynamic programming is now a standard tool for multistage planning in economics, robotics, control theory, and several other disciplines.

Reduction in space requirements

In many dynamic programming algorithms, it isn’t necessary to retain all intermediate results throughout the entire computation. For example, we can significantly reduce the space requirements of our algorithm $IterFibo$ by maintaining only the two newest elements of the array:

$\underline{IterFibo2(n):} \\ \hspace{0.4cm} prev←1 \\ \hspace{0.4cm} curr←0 \\ \hspace{0.4cm} for\space i ← 1\space to\space n \\ \hspace{1cm} next ← curr + prev \\ \hspace{1cm} prev ← curr \\ \hspace{1cm} curr ← next \\ \hspace{0.4cm} return\space curr$ ...