Tabulation

Tabulation

Tabulation is a technique used to solve problems.

Tabulation uses a table where the results to the most basic subproblems are stored first. The table then gets filled with more and more subproblem results until we find the result to the complete problem that we are looking for.

The tabulation technique is said to solve problems "bottom-up" because of how it solves the most basic subproblems first.

Tabulation is a technique used in Dynamic Programming, which means that to use tabulation, the problem we are trying to solve must consist of overlapping subproblems.

Using Tabulation To Find The \(n\)th Fibonacci Number

The Fibonacci numbers are great for demonstrating different programming techniques, also when demonstrating how tabulation works.

Tabulation uses a table that is filled with the lowest Fibonacci numbers \(F(0)=0\) and \(F(1)=1\) first (bottom-up). The next Fibonacci number to be stored in the table is \(F(2)=F(1)+F(0)\).

The next Fibonacci number is always the sum of the two previous numbers:

\[ F(n)=F(n-1)+F(n-2) \]

In this way, the table continues to get filled with next Fibonacci numbers until we find the \(n\)th Fibonacci number that we are looking for.

def fibonacci_tabulation(n):
    if n == 0: return 0
    elif n == 1: return 1

    F = [0] * (n + 1)
    F[0] = 0 
    F[1] = 1

    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]
    
    print(F)
    return F[n]
  
n = 10
result = fibonacci_tabulation(n)
print(f"\nThe {n}th Fibonacci number is {result}")

Other ways to find the \(n\)th Fibonacci number include recursion, or the improved version of it using memoization.

Tabulation Is A Bottom Up Approach

See the drawings below to get a better idea of why tabulation is called a "bottom up" approach.

As a reference to compare with, see the drawing of the "top-down" recursion approach to finding the \(n\)th Fibonacci number.

The tabulation approach starts building the table bottom up to find the 10th Fibonacci number, starting with \(F(0)\) and \(F(1)\).

The recursive approach start by trying to find \(F(10)\), but to find that it must call \(F(9)\) and \(F(8)\), and so it goes all the way down to \(F(0)\) and \(F(1)\) before the function calls start returning values that can be put together to the final answer.

Other Problems That Are Solved with Tabulation

Just like finding the \(n\)th Fibonacci number, tabulation can also be used to find the solution to other problems:

• The 0/1 Knapsack Problem is about having a set of items we can pack in a knapsack (a simple backpack), each item with a different value. To solve the problem we need to find the items that will maximize the total value of items we pack, but we cannot bring all the items we want because the knapsack has a weight limit.
• The Shortest Path Problem can be solved using the Bellman-Ford algorithm, which also uses tabulation to find the shortest paths in a graph. More specifically, the tabulation approach of the Bellman-Ford algorithm is in how the values in the "distances" array gets updated.
• The Traveling Salesman Problem can be solved precisely using the Held-Karp algorithm, which also uses tabulation. This algorithm is not described in this tutorial as it is although better than brute force \(O(n!)\), still not very effective \(O(2^n n^2)\), and quite advanced.

Tabulation in Dynamic Programming

As mentioned in the top, tabulation (just like memoization) is a technique used in something called Dynamic Programming.

Dynamic Programming is a way of designing algorithms to solve problems.

For Dynamic Programming to work, the problem we want to solve must have these two properties:

• The problem must be built up by smaller, overlapping subproblems. For example, the solution to Fibonacci number \(F(3)\) overlaps with the solutions to Fibonacci numbers \(F(2)\) and \(F(1)\), because we get \(F(3)\) by combining \(F(2)\) and \(F(1)\).
• The problem must also have an optimal substructure, meaning that the solution to the problem can be constructed from the solutions to its subproblems. When finding the \(n\)th Fibonacci number, \(F(n)\) can be found by adding \(F(n-1)\) and \(F(n-2)\). So knowing the two previous numbers is not enough to find \(F(n)\), we must also know the structure so that we know how to put them together.

Read more about Dynamic Programming on the next page.