Memoizing Fibonacci Numbers
Learn how to reduce the time complexity of the Fibonacci function using memoization.
We'll cover the following...
Let’s memoize the code now and see where that leads us. The basic idea is to check if a list already contains the result of the Fibonacci number that we are trying to find before calculating it.
Memoized code
Have a look at the complete 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 numbers.</param>/// <returns>The nth Fibonacci number.</returns>public static int Fib(int num, int[] lookupTable){if (lookupTable[num] == -1) // Check if already present{// Adding entry to table when not presentif (num <= 1){lookupTable[num] = num;}else{lookupTable[num] = Fib(num - 1, lookupTable) + Fib(num - 2, lookupTable);}}return lookupTable[num];}// Driver code to test above methodpublic static void Main(string[] args){int num = 6; // Finding the nth Fibonacci numberint[] lookupTable = new int[num + 1]; // Initializing the lookup table to have -1 of size num + 1for (int i = 0; i <= num; i++){lookupTable[i] = -1;}Console.WriteLine(Fib(num, lookupTable)); // Output: 8}}
The method is very simple. It takes as input the following:
- The number
n
that represents the Fibonacci number that we want to find, which is6
in our case. - A