Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Tabulating Fibonacci Numbers

Explore how to efficiently calculate Fibonacci numbers using dynamic programming's tabulation method in C#. Understand the bottom-up iterative approach, see step-by-step optimized implementations, and grasp improvements in time and space complexity.

We'll cover the following...

The tabulation approach is like filling up a table from the start. Let’s now find the nthn^{th} 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#:

C# 9.0
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 values
        lookupTable[0] = 0;
        lookupTable[1] = 1;
        for (int i = 2; i <= num; i++)
        {
            // Fill up the table by summing up previous two values
            lookupTable[i] = lookupTable[i - 1] + lookupTable[i - 2];
        }
        return lookupTable[num]; // Return the nth Fibonacci number
    }
    // Driver code to test above function
    public 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) and Fib(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:

fib(0)=0fib(0) = 0 ...