Fibonacci Numbers–Iterative Approach
Learn to solve Fibonacci numbers using the iterative approach with memoization.
Once we see how the array 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
Implementation
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 arrayF
of sizen+1
.
Now the time analysis is immediate: clearly uses and stores 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 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 by maintaining only the two newest elements of the array:
Algorithm
...
Create a free account to access the full course.
By signing up, you agree to Educative's Terms of Service and Privacy Policy