## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

DSA Linked Lists DSA Linked Lists in Memory DSA Linked Lists Types Linked Lists Operations

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# 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.

### Example

Finding the 10th Fibonacci number using tabulation:

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}")
Run Example ยป

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.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com