The temperature for the next week or so in the Twin Cities of Minneapolis and St. Paul will be in the lower 90F’s. That is rather hot for this time of the year. Due to this fact, my wife and I will be having breakfast as usual and then heading out for our daily walk. This way we should avoid the high temperatures in the afternoon hours and in addition most bugs. Most bugs then to come out in the late afternoon hours.
Friends in Peru have been sending my wife and me messages with the current results of the presidential election that took place this past Sunday. At this time it seems that the democratic candidate is slightly ahead of the communist one. Not sure how long it would take to have a final count but there is a lot of animosity in the air. If interested you can check what is happening with the vote tallies on the internet.
I continue to watch and experiment as I go with the contents of the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. The current problem is around 03:11:14 in the video. This video is about 5-hours long.
Write a function `fib(n)` that takes in a number as an argument. The function should return the n-th number of the Fibonacci sequence. The 0th number of the sequence is 0. The 1st number of the sequence is 1. To generate the next number of the sequence, we sum the previous two.
Earlier in this video we covered the Fibonacci sequence. If interested, you can read the post Fibonacci Revisited in this blog.
The Fibonacci Numbers are a sequence of integers that start with numbers 0 and 1. From then on the next number is the sum of the two previous ones. The description seems to lend itself very well for a recursive implementation. That is the approach we had in the previous post. In this post we will use tabulation which uses a loop (no recursion). Tabulation is the second approach besides memoization used in dynamic programming.
The instructor in the YouTube video makes use of the JavaScript programming language. We will use in this post Java, the VSCode IDE running on a Windows 10 computer. In general with both languages you should be able to run on most (never generalize) platforms without issues.
long fib(int n) {
}
The signature for the function in question in Java is quite simple. We are given `n` and need to return the Fibonacci associated with `n`.
0 main <<< n: 0 main <<< fib: 0 1 main <<< n: 1 main <<< fib: 1 2 main <<< n: 2 main <<< fib: 1 6 main <<< n: 6 main <<< fib: 8 7 main <<< n: 7 main <<< fib: 13 8 main <<< n: 8 main <<< fib: 21 50 main <<< n: 50 main <<< fib: 12586269025
Our test scaffold reads the first line of a test cases which represents `n`. The number is then displayed.
The program then calls the function in question which displays the result.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read n ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// **** compute and display Fibonacci number ****
System.out.println("main <<< fib: " + fib(n));
}
Not much to add to the test scaffold. It is short and simple.
/**
* Write a function `fib(n)` that takes in a number as an argument.
* The function should return the n-th number of the Fibonacci sequence.
*
* The 0th number of the sequence is 0.
* The 1st number of the sequence is 1.
*
* To generate the next number of the sequence, we sum the previous two.
*
* 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*
* Tabulation approach.
*
* Time: O(n) Space: O(n)
*/
static long fib(int n) {
// **** sanity check(s) ****
if (n == 0) return 0;
if (n == 1) return 1;
// **** initialization ****
long[] fibSeq = new long[n + 1];
fibSeq[1] = 1;
// **** loop filling the array ****
for (int i = 2; i <= n; i++)
fibSeq[i] = fibSeq[i - 2] + fibSeq[i - 1];
// **** return result ****
return fibSeq[n];
}
We start our function of interest by performing a couple sanity checks.
The initialization consists of creating an array of the proper size and initializing the first two entries. Note that in Java we just need to initialize the second entry because arrays are initialized with value 0.
We then loop adding the two prior values to the current one.
When done we return the last entry in the array.
Note that we could just use an array of two entries instead of the longer `fibSeq` array. This was not done because in this post we are interested in tabulation which not always allow us to replace the longer array.
I like that this approach is fast because it does not make use of recursion. Space is only allocated for the array. Stack allocation for recursion is not required.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John