Tabulating Fibonacci Numbers
Explore how tabulation can improve the efficiency of finding the nth Fibonacci number.
We'll cover the following...
We'll cover the following...
The tabulation approach is like filling up a table from the start. Let’s now find the Fibonacci number using bottom-up tabulation. This approach uses iteration and can essentially be thought of as recursive in reverse.
Tabulated version 1
Have a look at the tabulated code in C#:
using System;class Program{/// <summary>/// Finds the nth Fibonacci number./// </summary>/// <param name="num">An integer number.</param>/// <param name="lookupTable">Stores already calculated fibonacci number.</param>/// <returns>The nth Fibonacci number.</returns>public static int Fib(int num, int[] lookupTable){// Set 0th and first valueslookupTable[0] = 0;lookupTable[1] = 1;for (int i = 2; i <= num; i++){// Fill up the table by summing up previous two valueslookupTable[i] = lookupTable[i - 1] + lookupTable[i - 2];}return lookupTable[num]; // Return the nth Fibonacci number}// Driver code to test above functionpublic static void Main(string[] args){int num = 6;int[] lookupTable = new int[num + 1];Console.WriteLine(Fib(num, lookupTable)); // Output: 8}}
This algorithm does the following:
- Initializes a lookup table and sets the values of
Fib(0)
andFib(1)
, as those are the base cases on lines 14–15. - Finds out the values of the rest of the Fibonacci numbers by summing up the values of the previous two (line 20).
The following lines explain how the code works:
...