Blog

Master Dynamic Programming and Its 2 Techniques: Memoization and Tabulation

Dynamic Programming (DP) is a technique used to solve complex problems by breaking them down into simpler subproblems. Solving each subproblem once and storing the results can prevent redundant work and speed up the solution process. In this article, we’ll explore the basics of Dynamic Programming, dive into two key techniques—memoization and tabulation—and provide detailed Java code examples to help you understand how to implement these methods.

What is Dynamic Programming?

DP solves problems by dividing them into smaller subproblems, solving each subproblem only once, and storing the results. When a subproblem needs to be solved again, the stored result is used, which saves time by avoiding repeated calculations. This technique is most useful when the problem has two key features:

  1. Overlapping Subproblems: The problem can be divided into smaller parts, and these smaller parts overlap, meaning the same subproblems are solved multiple times.
  2. Optimal Substructure: The optimal solution to the problem can be constructed from the optimal solutions to its subproblems.

Also check: Sliding Window Algorithm – Fixed and Variable-Length Solutions

Real-World Example

Leetcode Problem: Fibonacci Number

We will be using this example to demonstrate how the two techniques of dynamic programming, namely memoization and tabulation work as mentioned in the sections below.

Imagine you’re trying to find the shortest path between two cities. If you keep recalculating the shortest path between the same intermediate cities, it becomes inefficient. With DP, you can store the results of these intermediate paths and reuse them, making your solution much faster.

Why Do We Need Dynamic Programming?

While recursion is a powerful tool for solving problems, it becomes inefficient for certain problems due to redundant calculations. A classic example of this inefficiency is the Fibonacci sequence.

Fibonacci Sequence Example: Recursion vs. Dynamic Programming

Consider the problem of calculating the nth Fibonacci number. The Fibonacci sequence is defined as follows:

  • Fibonacci(0) = 0
  • Fibonacci(1) = 1
  • Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) for n > 1

Recursive Solution (Naive Approach)

Let’s first look at a naive recursive solution for calculating Fibonacci numbers. Although the code is simple, it leads to many redundant calculations, which makes it inefficient.

public class FibonacciRecursive {

    // Naive recursive approach to calculate Fibonacci
    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2); // Recurse for the previous two Fibonacci numbers
    }

    public static void main(String[] args) {
        int n = 4;  // Calculate the 10th Fibonacci number
        System.out.println("Fibonacci number at position " + n + " is: " + fib(n));
    }
}

As can be seen below, the call for fib(4) calls fib(3) & fib(2). fib(3) in turn calls fib(2) & fib(1). fib(2) in turn calls fib(1) & fib(0). There are some repetitive calls such as fib(2), fib(1) & fib(0).

Dynamic Programming

How This Approach Works:

  1. The function fib(n) calculates the nth Fibonacci number by recursively calling fib(n-1) and fib(n-2).
  2. This process repeats for each number, creating a binary recursion tree.
  3. However, you can see that many Fibonacci numbers are computed repeatedly. For example, fib(2) is calculated twice, fib(1) is calculated three times, and so on.

Time Complexity of the Recursive Solution:

  • The time complexity of this approach is O(2^n), which is exponential. As n keeps growing, the number of recursive calls grows rapidly, and this becomes highly inefficient for large values of n.

Why is This Inefficient?

In the naive recursive solution, the same subproblems are solved multiple times. For instance, to compute fib(4), the function recalculates fib(2) and fib(1) multiple times. This redundant work is a key reason why recursion alone is inefficient for problems with overlapping subproblems, like Fibonacci.

Memoization Tabulation

If you look at the image above, the same color codes are assigned to the recurring subproblems. For fib(4), fib(2) & fib(0) are called twice and fib(1) is called thrice. If we store fib(2), fib(1) & fib(0) the first time they are called, we won’t need to compute it again when it is called subsequently. This is exactly what dynamic programming does. And solves problems efficiently.

Key Techniques of Dynamic Programming

There are two main ways to implement DP: Memoization and Tabulation. Let’s take a closer look at each technique.

1. Memoization

Memoization is a top-down approach where you solve the problem recursively and store the results of subproblems. Before solving a subproblem, you check if it has been solved before. If it has, you use the stored result instead of recomputing it.

In simple terms, memoization helps you avoid redundant calculations by storing and reusing results.

Example of Memoization: Fibonacci Numbers

The Fibonacci numbers are a classic example of a problem that benefits from memoization. In the Fibonacci sequence, each number is the sum of the two preceding ones. A simple recursive approach can be slow because it calculates the same subproblems multiple times. Memoization reduces this inefficiency.

Here’s a Java example of how to calculate the nth Fibonacci number using memoization:

import java.util.HashMap;

public class FibonacciMemoization {

    private static HashMap<Integer, Integer> memo = new HashMap<>();

    // Function to calculate the nth Fibonacci number
    public static int fib(int n) {
        // Base case: Fibonacci of 0 is 0, Fibonacci of 1 is 1
        if (n <= 1) {
            return n;
        }

        // Check if the result is already stored
        if (memo.containsKey(n)) {
            return memo.get(n); // Return cached result
        }

        // Calculate Fibonacci number and store it
        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result); // Store the result

        return result;
    }

    public static void main(String[] args) {
        int n = 4;  // Calculate the 10th Fibonacci number
        System.out.println("Fibonacci number at position " + n + " is: " + fib(n));
    }
}

Explanation of the Code

  1. Base Case: If n is 0 or 1, return n directly because the first two Fibonacci numbers are predefined.
  2. Memoization Check: Before doing any calculations, the function checks if the result for fib(n) is already in the memo map. If it exists, it returns the cached value.
  3. Recursive Calculation: If the result is not cached, the function calculates it by calling fib(n – 1) and fib(n – 2). The result is stored in memo for future reference.

Advantages of Memoization

  • Improved Performance: It reduces the time complexity from O(2^n) in naive recursion to O(n).
  • Simplicity: It’s easy to implement for recursive problems.

Time Complexity: O(n), where n is the input value.
Space Complexity: O(n) for storing the results in the memo map.

2. Tabulation

Tabulation is a bottom-up approach where you solve the problem iteratively. You start by solving the smallest subproblems and use their results to build up the solution to the original problem. This approach typically uses an array or table to store the results.

Unlike memoization, tabulation does not involve recursion.

Example of Tabulation: Fibonacci Numbers

Let’s now solve the Fibonacci problem using tabulation. In this case, we’ll build up the solution iteratively and store the results in an array.

Here’s a Java implementation of Fibonacci using tabulation:

public class FibonacciTabulation {

    // Function to calculate the nth Fibonacci number
    public static int fib(int n) {
        // If n is 0 or 1, return n as the base case
        if (n <= 1) {
            return n;
        }

        // Create an array to store Fibonacci numbers up to n
        int[] dp = new int[n + 1];

        // Initialize the base cases
        dp[0] = 0; // Fibonacci(0)
        dp[1] = 1; // Fibonacci(1)

        // Fill the dp array iteratively for all Fibonacci numbers up to n
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // Fibonacci relation
        }

        // Return the nth Fibonacci number
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 4;  // Calculate the 10th Fibonacci number
        System.out.println("Fibonacci number at position " + n + " is: " + fib(n));
    }
}

Explanation of the Code

  1. Base Case Initialization: We initialize the first two Fibonacci numbers, dp[0] = 0 and dp[1] = 1.
  2. Iterative Calculation: Starting from i = 2, we calculate each Fibonacci number iteratively using the relation dp[i] = dp[i – 1] + dp[i – 2].
  3. Final Result: After filling the table, the nth Fibonacci number is stored in dp[n], and we return it.

Advantages of Tabulation

  • Efficiency: It avoids recursion, making it more efficient, especially for large inputs.
  • No Recursion: It doesn’t involve the overhead of recursive calls, making it more space-efficient in some cases.

Time Complexity: O(n), where n is the input value.
Space Complexity: O(n) for the dp array.

Also check: Greedy Algorithm: A Comprehensive Guide With Examples

More Advanced Dynamic Programming Problems

DP is useful for much more than just Fibonacci numbers. Let’s explore some more complex problems where dynamic programming is highly effective.

1. Knapsack Problem (0/1 Knapsack)

The Knapsack Problem involves selecting items with given weights and values to maximize the total value while staying within a weight limit. The challenge is to decide which items to include in the knapsack to achieve the highest total value.

Example: 0/1 Knapsack

Here’s how to solve the 0/1 knapsack problem using DP:

Memoization Implementation:

import java.util.HashMap;

public class KnapsackMemoization {
    
    private static HashMap<String, Integer> memo = new HashMap<>();
    
    public static int knapsack(int[] weights, int[] values, int n, int W) {
        // Base case: no items left or no capacity in the knapsack
        if (n == 0 || W == 0) {
            return 0;
        }
        
        // Check if result is already computed
        String key = n + "-" + W;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        // If the current item is too heavy, don't include it
        if (weights[n - 1] > W) {
            return knapsack(weights, values, n - 1, W);
        }
        
        // Compute both possibilities: including or excluding the item
        int include = values[n - 1] + knapsack(weights, values, n - 1, W - weights[n - 1]);
        int exclude = knapsack(weights, values, n - 1, W);
        
        // Store and return the maximum value
        int result = Math.max(include, exclude);
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 5;
        int n = weights.length;

        System.out.println("Maximum value in Knapsack = " + knapsack(weights, values, n, W));
    }
}

Tabulation Implementation:

public class KnapsackTabulation {

    public static int knapsack(int[] weights, int[] values, int W, int n) {
        // dp[i][j] stores the maximum value for the first i items and weight j
        int[][] dp = new int[n + 1][W + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int W = 5;
        int n = weights.length;

        System.out.println("Maximum value in Knapsack = " + knapsack(weights, values, W, n));
    }
}

2. Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that appears in both of two given strings.

Memoization Implementation:

import java.util.HashMap;

public class LCSMemoization {
    
    private static HashMap<String, Integer> memo = new HashMap<>();

    public static int lcs(String s1, String s2, int m, int n) {
        // Base case: if either string is empty
        if (m == 0 || n == 0) {
            return 0;
        }

        String key = m + "-" + n;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // If the characters match, include it in the LCS
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            int result = 1 + lcs(s1, s2, m - 1, n - 1);
            memo.put(key, result);
            return result;
        }

        // Otherwise, take the maximum of excluding one character from either string
        int result = Math.max(lcs(s1, s2, m - 1, n), lcs(s1, s2, m, n - 1));
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";
        System.out.println("Length of LCS is " + lcs(s1, s2, s1.length(), s2.length()));
    }
}

Tabulation Implementation:

public class LCSTabulation {

    // Function to calculate the length of the Longest Common Subsequence (LCS)
    public static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        
        // Create a 2D array to store the lengths of LCS for different substrings
        int[][] dp = new int[m + 1][n + 1];

        // Build the dp array from the bottom-up
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If the characters match, increment the length of LCS by 1
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // Otherwise, take the maximum length between excluding the current character
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // The length of the LCS will be stored at dp[m][n]
        return dp[m][n];
    }

    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        // Call the LCS function and print the result
        System.out.println("Length of LCS is " + lcs(s1, s2));
    }
}

Conclusion

Dynamic Programming is a powerful technique for solving complex problems efficiently by breaking them down into smaller subproblems. By using memoization or tabulation, you can save time and improve performance significantly. Memoization uses recursion and stores results for reuse, while tabulation uses iteration to fill a table and avoid recursion. Both methods have their strengths, and the choice between them depends on the problem at hand.

That’s all on the Dynamic Programming algorithm and its two techniques: memoization and tabulation.

To keep yourself up to date with our latest content, please subscribe to our newsletter by dropping your email address here: Signup for Our Newsletter.

Please follow us on Medium.

Further Reading