Home/Blog/Programming/Memoization vs. tabulation in dynamic programming

Memoization vs. tabulation in dynamic programming

Hassan Shahzad

Nov 13, 2024

11 min read

What is dynamic programming?#

Have you ever wanted to avoid fixing the same problem over and over again? That’s made achievable by dynamic programming (DP). Consider it similar to reusing short snippets of code to save time. Instead of recalculating answers, DP divides a large problem into smaller ones, solves each once, and saves the results for later use.
Dynamic Programming(DP) is a technique used to simplify complex problems by dividing them into manageable subproblems. It’s especially useful in optimization scenarios, where partial solutions can be combined to solve the overall problem. The key idea is to store results from earlier steps so they don’t have to be recalculated, saving time and making the process much more efficient. Dynamic programming solves problems by breaking them into smaller subproblems and reusing solutions. This can be done using two main techniques:

Memoization: Imagine solving a problem recursively but caching the results so you never have to redo the same work—this is memoization, a top-down approach. It saves the outputs of expensive function calls and reuses them when the same inputs appear again. Memoization typically uses recursion and stores intermediate results in a dictionary or hash map to avoid redundant calculations.
Tabulation: On the other hand, tabulation is a bottom-up approach. Think of it as building the solution step-by-step, starting with the smallest subproblems and using their outcomes to solve the larger problem. It depends on iteration and uses an array to hold the results of each subproblem, gradually calculating the final answer.

This blog will discuss the following two problems and examine their implementation using memoization and tabulation techniques. Their problem statements are as follows:

Fibonacci numbers: Fibonacci numbers often begin with 0 and 1 are a sequence of numbers where each is the sum of the two numbers that came before. The sequence is defined as:
$F(0) = 0$
$F(1) = 1$
$F(n) = F(n-1) + F(n-2)~for~ n ≥ 2$
The Fibonacci sequence is as follows: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...$
House Robber: In the House Robber problem, thieves must take as much money as possible from a row of houses. A specific quantity of cash is hidden in each home. However, a thief cannot take money from two houses next to one another. The goal is to steal from two houses to calculate the largest amount of money that may be taken.

Memoization technique#

Memoization keeps the results of expensive function calls to maximize recursive algorithms’ performance. Instead of recalculating the results, the cached results are used when the identical inputs are entered again. This technique keeps track of a cache, usually implemented as a dictionary or hash table with the computed results as the values and the function’s input parameters as the keys. Before being called, a function determines whether the result is already cached. If so, the cached result is instantly given back. If not, the function is computed, and the result is stored in the cache for future use.

Dynamic Programming in Python: Optimizing Programs for Efficiency

Dynamic programming is something every developer should have in their toolkit. It allows you to optimize your algorithm with respect to time and space — a very important concept in real-world applications. In this course, you’ll start by learning the basics of recursion and work your way to more advanced DP concepts like Bottom-Up optimization. Throughout this course, you will learn various types of DP techniques for solving even the most complex problems. Each section is complete with coding challenges of varying difficulty so you can practice a wide range of problems. By the time you’ve completed this course, you will be able to utilize dynamic programming in your own projects.

8hrs

Intermediate

16 Challenges

3 Quizzes

Memoization example: Fibonacci numbers#

Here’s a step-by-step explanation of the algorithm:

Initialize a dictionary (or any suitable data structure) to store the results of Fibonacci calculations.
Define a function fib(n, cache), where n is the Fibonacci number to compute and cache is the cache to store the function calls.
Check if n is already in cache. If it is, return cache[n].
If n is less than or equal to $1$ , return n (base case).
Compute fib(n-1, cache) + fib(n-2, cache), store the result in cache[n], and return it.

Look at the following illustration to get a better understanding of the algorithm:

def fib(n, cache={}):
    # If the value is already in cache, return it
    if n in cache:
        return cache[n]
    
    # Base case: Return n if n is 0 or 1
    if n <= 1:
        return n
    
    # Recursive case: Compute the value and store it in the cache
    cache[n] = fib(n-1, cache) + fib(n-2, cache)
    
    return cache[n]
n = [10, 5, 15, 1, 8]
for i, number in enumerate(n):
    print(f"{i+1}.\tn = ", number)
    print(f"\tFib({number}) = ", fib(number))
    print("-"*100)

Fibonacci Numbers using memoization

Complexity analysis#

Time complexity: The time complexity of this solution is $O(n)$ because the function computes the Fibonacci value for each number from $0$ to $n$ exactly once.

Space complexity: The space complexity of this solution is $O(n)$ because the cache stores the Fibonacci values for each number from $0$ to $n$ .

Memoization example: House robber#

Here’s a step-by-step explanation of the algorithm:

Create a function rob that takes the list of houses and the current index n as arguments. Use a dictionary cache to store the results of subproblems.
Base cases:
- If n is $0$ , return the money stolen from the first house.
- If n is $1$ , return the maximum money between the first and second houses.
Before computing the result for the current house n, check if it is already in the cache. If yes, return the cached value.
For each house n, the thief has two choices:
- Skip the current house and move to the previous house n-1.
- Steal from the current house and skip the adjacent house n-2.
- The value of a house n is the maximum of:
  - The value of the $n-1$ house.
  - The value of the current house plus the value of the $n-2$ house.
Store the computed result in the cache and return it.

Look at the following illustration to get a better understanding of the algorithm:

def rob(house, n, cache):
    # Check if the result for the current house is already cached
    if n in cache:
        return cache[n]
    # Base case: Only one house to steal from
    if n == 0:
        return house[0]
    # Base case: Only two houses to choose from, take the maximum
    if n == 1:
        return max(house[0], house[1])
    
    # Recursively compute the maximum stolen value and cache the result
    cache[n] = max(rob(house, n-1, cache), house[n] + rob(house, n-2, cache))
    
    return cache[n]
houses = [
    [6, 7, 1, 30, 8, 2, 4],
    [20, 25, 30, 15, 10, 5, 50],
    [5, 3, 4, 11, 2],
    [3, 2, 5, 10, 7],
    [6, 7, 8, 2, 4]
]
for i, loot in enumerate(houses):
    n = len(loot) - 1
    print(f"{i+1}.\tHouse = ", loot)
    print("\tMaximum loot = ", rob(loot, n, {}))
    print("-"*100)

House Robber using memoization

Tabulation technique#

In dynamic programming, tabulation is a bottom-up method where all subproblems are solved first, and the larger problems are solved using the calculated solutions. Tabulation utilizes iteration and saves results in a table, unlike memoization, which utilizes recursion and keeps results in a cache. This approach ensures that each subproblem is addressed exactly once and in a specific order by building a table from the smallest subproblems to the main problem.

Tabulation example: Fibonacci numbers#

Here’s a step-by-step explanation of the algorithm:

Create an array table to store the Fibonacci results.
Set the initial values for F(0) and F(1) in the array.
Iterate from i = 2 to n, filling the array with F(i) = F(i−1) + F(i−2).
The value at the $n^{th}$ index of the array is F(n).

Look at the following illustration to get a better understanding of the algorithm:

Complexity analysis#

Time complexity: The time complexity of this solution is $O(n)$ because each subproblem is solved iteratively exactly once. The time complexity is linear as the houses are iterated over a total of $(n−1)$ times.

Space complexity: The space complexity of this solution is $O(n)$ , where $n$ is the total number of houses. The reason is the space used by the array, which is $n$ because the array is filled once for each subproblem.

Tabulation example: House robber#

Here’s a step-by-step explanation of the algorithm using tabulation:

Start by checking for the following base cases:
- If houses is empty, return $0$ because there are no houses to steal from.
- If there is only one house, return the amount of money in that house.
- If there are two houses, return the maximum money between them, as the thief can only rob one.
Initialize a list table to store the maximum amount of money that can be stolen from each house. The table’s length is the same as the number of houses.
Set the first element of the table to the value of the first house and the second element of the table to the maximum value between the first and second house.
Iterate over the remaining houses, from the third house (index $2$ ) to the last. For each house at the index i, calculate the maximum amount of money that can be stolen by considering one of the two choices:
- The maximum money was stolen up to the previous house table[i - 1].
- The value of the houses[i] + table[i - 2].
Return the last element of the table, which represents the maximum amount of money that can be stolen from all houses.

Look at the following illustration to get a better understanding of the algorithm:

def rob(houses):
    # If there are no houses, the maximum money stolen is 0
    if not houses:
        return 0
    
    # If there is only one house, steal from it
    if len(houses) == 1:
        return houses[0]
    
    # If there are two houses, steal from the one with the most money
    if len(houses) == 2:
        return max(houses[0], houses[1])
    # Create a table to store the maximum money stolen up to each house
    table = [0] * len(houses)
    table[0] = houses[0]
    table[1] = max(houses[0], houses[1])
    # Fill the table using the bottom-up approach
    for i in range(2, len(houses)):
        table[i] = max(table[i - 1], houses[i] + table[i - 2])
    # The last element in the table contains the maximum money that can be stolen
    return table[-1]
houses = [
    [6, 7, 1, 30, 8, 2, 4],
    [20, 25, 30, 15, 10, 5, 50],
    [5, 3, 4, 11, 2],
    [3, 2, 5, 10, 7],
    [6, 7, 8, 2, 4]
]
for i, loot in enumerate(houses):
    print(f"{i+1}.\tHouse = ", loot)
    print("\tMaximum loot = ", rob(loot))
    print("-"*100)

House Robber using tabulation

Complexity analysis#

Time complexity: The time complexity of this solution is $O(n)$ because each subproblem is solved iteratively exactly once. The complexity is linear becuase houses are iterated over a total of $(n−2)$ times.

Memoization vs. Tabulation#

Let’s refer to the following comparison table to understand the key differences and best use cases for memoization and tabulation:

Comparison Table

Feature	Memoization	Tabulation
Approach	Top-down	Bottom-up
Data structure used	Uses a cache, typically a hash table or dictionary.	Uses a table, typically a 2D array or similar structure.
Function calls	Recursive	Iterative
Initialization	Only the required entries are initialized.	All entries are initialized.
Problem-solving approach	Starts by identifying the primary problem and breaking it into smaller subproblems.	Starts with the smallest subproblems and gradually solves them to tackle the main problem.
Space complexity	Depends on the depth of the recursion tree.	Generally more predictable and often uses more space initially.
Use cases	Suitable for problems where subproblems are solved multiple times.	Suitable for problems where the order of subproblems is clear and can be solved sequentially.

Best practices in dynamic programming#

Dynamic programming (DP) is useful for addressing problems by dividing them into smaller subproblems and solving each subproblem only once. One must understand and use best practices to fully understand the DP concepts. This calls for an organized approach to analyzing, formulating, and optimizing problems.

Analyzing the problem#

Before coding, thoroughly understand the problem.
Determine whether it contains the overlapping subproblems and optimal substructure important to dynamic programming problems.
Divide the problem into more manageable subproblems, and think about the associations between these smaller problems. For example, every number in the Fibonacci number equals the sum of the two numbers that came before it.

Optimizing space and time complexity#

When implementing a DP solution, always optimize space and time complexity. Memoization stores the results of subproblems to avoid redundant calculations, but it can use much memory. On the other hand, tabulation uses an iterative approach, which can sometimes be optimized to use less space. For example, in the Fibonacci numbers, you only need to store the last two computed values rather than the whole sequence. Always look for opportunities to reduce your solution’s space and time requirements.

Common pitfalls and how to avoid them#

Several common pitfalls can cause a significant problem even for experienced developers working with dynamic programming. Recognizing and understanding how to avoid these issues will make your dynamic programming solutions more efficient and reliable. Let’s look at some of them:

Overlapping subproblems#

One common pitfall in dynamic programming is not recognizing overlapping subproblems. This leads to recalculating the same results multiple times, which can significantly slow down your algorithm. To avoid this, ensure you are using memoization or tabulation to store the results of subproblems. By doing so, you only compute each subproblem once, thus optimizing the performance of your solution.

Incorrect base/boundary cases#

Another common mistake is incorrectly defining base and boundary cases. Base and boundary cases are the simplest possible subproblems and serve as the stopping point for recursion and iteration, respectively. Your algorithm can produce incorrect results or enter infinite loops if these are not correctly defined. Always double-check your base and boundary cases to ensure they accurately represent the simplest form of the problem. For example, in the Fibonacci numbers, the base cases are $F(0)=0$ and $F(1)=1$ .

Test yourself#

Let’s recall the dynamic programming techniques. Match the correct option with the appropriate dynamic programming technique: Memoization vs. Tabulation.

Match The Answer

Select an option from the left-hand side

Typically uses a fixed amount of space in an iteratively, avoiding stack overflow.

Memoization

The top-down approach is where results of subproblems are stored and reused.

Tabulation

Often easier to implement for problems naturally defined recursively.

Iterative, solving the problem from the bottom and building up.

A bottom-up approach is where results of subproblems are computed and stored iteratively.

Uses a cache (e.g., dictionary or hash table) to store results of subproblems.

Conclusion#

Dynamic programming is a powerful method for solving problems that involve overlapping subproblems and optimal substructure. Key best practices include thoroughly analyzing the problem, optimizing space and time complexity, and carefully defining base cases. Becoming proficient in dynamic programming requires practice. Regularly solving DP problems helps you recognize patterns and improve your ability to formulate DP solutions. Start with simpler problems and gradually move to more complex ones.

Memoization vs. tabulation in dynamic programming

What is dynamic programming?#

Memoization technique#

Memoization example: Fibonacci numbers#

Complexity analysis#

Memoization example: House robber#

Complexity analysis#

Tabulation technique#

Tabulation example: Fibonacci numbers#

Complexity analysis#

Tabulation example: House robber#

Complexity analysis#

Memoization vs. Tabulation#

Comparison Table

Best practices in dynamic programming#

Analyzing the problem#

Optimizing space and time complexity#

Common pitfalls and how to avoid them#

Overlapping subproblems#

Incorrect base/boundary cases#

Test yourself#

Conclusion#

Further reading#