Tabulating Fibonacci Numbers
Explore how tabulation can improve the efficiency of finding the nth Fibonacci number.
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:
...