Fibonacci Numbers–Iterative Approach

Learn to solve Fibonacci numbers using the iterative approach with memoization.

Once we see how the array F[ ]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.

Algorithm


IterFibo(n):F[0]0F[1]1for i2 to nF[i]F[i1]+F[i2]return F[n]\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]

Implementation

Press + to interact
public class main {
public static void main(String[] args) {
int result = IterFibo(6);
System.out.println(result);
}
public static int IterFibo(int n) {
int[] F = new int[n+1];
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++) {
F[i] = F[i-1] + F[i-2];
}
return F[n];
}
}

Explanation:

  • Lines 11–13: The for loop iteratively calculates the Fibonacci sequence using an integer array F of size n+1.

Now the time analysis is immediate: IterFiboIterFibo clearly uses O(n)additionsO(n) additions and stores O(n)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 Virahan.kaVirah\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” does not 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 is not necessary to retain all intermediate results throughout the entire computation. For example, we can significantly reduce the space requirements of our algorithm IterFiboIterFibo by maintaining only the two newest elements of the array:

Algorithm


IterFibo2(n):prev1curr0for i1 to nnextcurr+prevprevcurrcurrnextreturn curr\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 ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy